-
Distributed Convex Optimization "Over-the-Air" in Dynamic Environments
Authors:
Navneet Agrawal,
Renato L. G. Cavalcante,
Masahiro Yukawa,
Slawomir Stanczak
Abstract:
This paper presents a decentralized algorithm for solving distributed convex optimization problems in dynamic networks with time-varying objectives. The unique feature of the algorithm lies in its ability to accommodate a wide range of communication systems, including previously unsupported ones, by abstractly modeling the information exchange in the network. Specifically, it supports a novel comm…
▽ More
This paper presents a decentralized algorithm for solving distributed convex optimization problems in dynamic networks with time-varying objectives. The unique feature of the algorithm lies in its ability to accommodate a wide range of communication systems, including previously unsupported ones, by abstractly modeling the information exchange in the network. Specifically, it supports a novel communication protocol based on the "over-the-air" function computation (OTA-C) technology, that is designed for an efficient and truly decentralized implementation of the consensus step of the algorithm. Unlike existing OTA-C protocols, the proposed protocol does not require the knowledge of network graph structure or channel state information, making it particularly suitable for decentralized implementation over ultra-dense wireless networks with time-varying topologies and fading channels. Furthermore, the proposed algorithm synergizes with the "superiorization" methodology, allowing the development of new distributed algorithms with enhanced performance for the intended applications. The theoretical analysis establishes sufficient conditions for almost sure convergence of the algorithm to a common time-invariant solution for all agents, assuming such a solution exists. Our algorithm is applied to a real-world distributed random field estimation problem, showcasing its efficacy in terms of convergence speed, scalability, and spectral efficiency. Furthermore, we present a superiorized version of our algorithm that achieves faster convergence with significantly reduced energy consumption compared to the unsuperiorized algorithm.
△ Less
Submitted 10 July, 2023;
originally announced July 2023.
-
Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields
Authors:
Tatsuya Koyakumaru,
Masahiro Yukawa,
Eduardo Pavez,
Antonio Ortega
Abstract:
This paper presents a convex-analytic framework to learn sparse graphs from data. While our problem formulation is inspired by an extension of the graphical lasso using the so-called combinatorial graph Laplacian framework, a key difference is the use of a nonconvex alternative to the $\ell_1$ norm to attain graphs with better interpretability. Specifically, we use the weakly-convex minimax concav…
▽ More
This paper presents a convex-analytic framework to learn sparse graphs from data. While our problem formulation is inspired by an extension of the graphical lasso using the so-called combinatorial graph Laplacian framework, a key difference is the use of a nonconvex alternative to the $\ell_1$ norm to attain graphs with better interpretability. Specifically, we use the weakly-convex minimax concave penalty (the difference between the $\ell_1$ norm and the Huber function) which is known to yield sparse solutions with lower estimation bias than $\ell_1$ for regression problems. In our framework, the graph Laplacian is replaced in the optimization by a linear transform of the vector corresponding to its upper triangular part. Via a reformulation relying on Moreau's decomposition, we show that overall convexity is guaranteed by introducing a quadratic function to our cost function. The problem can be solved efficiently by the primal-dual splitting method, of which the admissible conditions for provable convergence are presented. Numerical examples show that the proposed method significantly outperforms the existing graph learning methods with reasonable CPU time.
△ Less
Submitted 17 September, 2021;
originally announced September 2021.
-
Relaxed Zero-Forcing Beamformer under Temporally-Correlated Interference
Authors:
Takehiro Kono,
Masahiro Yukawa,
Tomasz Piotrowski
Abstract:
The relaxed zero-forcing (RZF) beamformer is a quadratically-and-linearly constrained minimum variance beamformer. The central question addressed in this paper is whether RZF performs better than the widely-used minimum variance distortionless response and zero-forcing beamformers under temporally-correlated interference. First, RZF is rederived by imposing an ellipsoidal constraint that bounds th…
▽ More
The relaxed zero-forcing (RZF) beamformer is a quadratically-and-linearly constrained minimum variance beamformer. The central question addressed in this paper is whether RZF performs better than the widely-used minimum variance distortionless response and zero-forcing beamformers under temporally-correlated interference. First, RZF is rederived by imposing an ellipsoidal constraint that bounds the amount of interference leakage for mitigating the intrinsic gap between the output variance and the mean squared error (MSE) which stems from the temporal correlations. Second, an analysis of RZF is presented for the single-interference case, showing how the MSE is affected by the spatio-temporal correlations between the desired and interfering sources as well as by the signal and noise powers. Third, numerical studies are presented for the multiple-interference case, showing the remarkable advantages of RZF in its basic performance as well as in its application to brain activity reconstruction from EEG data. The analytical and experimental results clarify that the RZF beamformer gives near-optimal performance in some situations.
△ Less
Submitted 11 September, 2021;
originally announced September 2021.
-
Continuous-time Value Function Approximation in Reproducing Kernel Hilbert Spaces
Authors:
Motoya Ohnishi,
Masahiro Yukawa,
Mikael Johansson,
Masashi Sugiyama
Abstract:
Motivated by the success of reinforcement learning (RL) for discrete-time tasks such as AlphaGo and Atari games, there has been a recent surge of interest in using RL for continuous-time control of physical systems (cf. many challenging tasks in OpenAI Gym and DeepMind Control Suite). Since discretization of time is susceptible to error, it is methodologically more desirable to handle the system d…
▽ More
Motivated by the success of reinforcement learning (RL) for discrete-time tasks such as AlphaGo and Atari games, there has been a recent surge of interest in using RL for continuous-time control of physical systems (cf. many challenging tasks in OpenAI Gym and DeepMind Control Suite). Since discretization of time is susceptible to error, it is methodologically more desirable to handle the system dynamics directly in continuous time. However, very few techniques exist for continuous-time RL and they lack flexibility in value function approximation. In this paper, we propose a novel framework for model-based continuous-time value function approximation in reproducing kernel Hilbert spaces. The resulting framework is so flexible that it can accommodate any kind of kernel-based approach, such as Gaussian processes and kernel adaptive filters, and it allows us to handle uncertainties and nonstationarity without prior knowledge about the environment or what basis functions to employ. We demonstrate the validity of the presented framework through experiments.
△ Less
Submitted 30 November, 2018; v1 submitted 8 June, 2018;
originally announced June 2018.
-
Detection for 5G-NOMA: An Online Adaptive Machine Learning Approach
Authors:
Daniyal Amir Awan,
Renato L. G. Cavalcante,
Masahiro Yukawa,
Slawomir Stanczak
Abstract:
Non-orthogonal multiple access (NOMA) has emerged as a promising radio access technique for enabling the performance enhancements promised by the fifth-generation (5G) networks in terms of connectivity, low latency, and high spectrum efficiency. In the NOMA uplink, successive interference cancellation (SIC) based detection with device clustering has been suggested. In the case of multiple receive…
▽ More
Non-orthogonal multiple access (NOMA) has emerged as a promising radio access technique for enabling the performance enhancements promised by the fifth-generation (5G) networks in terms of connectivity, low latency, and high spectrum efficiency. In the NOMA uplink, successive interference cancellation (SIC) based detection with device clustering has been suggested. In the case of multiple receive antennas, SIC can be combined with the minimum mean-squared error (MMSE) beamforming. However, there exists a tradeoff between the NOMA cluster size and the incurred SIC error. Larger clusters lead to larger errors but they are desirable from the spectrum efficiency and connectivity point of view. We propose a novel online learning based detection for the NOMA uplink. In particular, we design an online adaptive filter in the sum space of linear and Gaussian reproducing kernel Hilbert spaces (RKHSs). Such a sum space design is robust against variations of a dynamic wireless network that can deteriorate the performance of a purely nonlinear adaptive filter. We demonstrate by simulations that the proposed method outperforms the MMSE-SIC based detection for large cluster sizes.
△ Less
Submitted 11 January, 2018; v1 submitted 1 November, 2017;
originally announced November 2017.
-
A stochastic behavior analysis of stochastic restricted-gradient descent algorithm in reproducing kernel Hilbert spaces
Authors:
Masa-aki Takizawa,
Masahiro Yukawa,
Cedric Richard
Abstract:
This paper presents a stochastic behavior analysis of a kernel-based stochastic restricted-gradient descent method. The restricted gradient gives a steepest ascent direction within the so-called dictionary subspace. The analysis provides the transient and steady state performance in the mean squared error criterion. It also includes stability conditions in the mean and mean-square sense. The prese…
▽ More
This paper presents a stochastic behavior analysis of a kernel-based stochastic restricted-gradient descent method. The restricted gradient gives a steepest ascent direction within the so-called dictionary subspace. The analysis provides the transient and steady state performance in the mean squared error criterion. It also includes stability conditions in the mean and mean-square sense. The present study is based on the analysis of the kernel normalized least mean square (KNLMS) algorithm initially proposed by Chen et al. Simulation results validate the analysis.
△ Less
Submitted 14 October, 2014;
originally announced October 2014.
-
Adaptive Learning in Cartesian Product of Reproducing Kernel Hilbert Spaces
Authors:
Masahiro Yukawa
Abstract:
We propose a novel adaptive learning algorithm based on iterative orthogonal projections in the Cartesian product of multiple reproducing kernel Hilbert spaces (RKHSs). The task is estimating/tracking nonlinear functions which are supposed to contain multiple components such as (i) linear and nonlinear components, (ii) high- and low- frequency components etc. In this case, the use of multiple RKHS…
▽ More
We propose a novel adaptive learning algorithm based on iterative orthogonal projections in the Cartesian product of multiple reproducing kernel Hilbert spaces (RKHSs). The task is estimating/tracking nonlinear functions which are supposed to contain multiple components such as (i) linear and nonlinear components, (ii) high- and low- frequency components etc. In this case, the use of multiple RKHSs permits a compact representation of multicomponent functions. The proposed algorithm is where two different methods of the author meet: multikernel adaptive filtering and the algorithm of hyperplane projection along affine subspace (HYPASS). In a certain particular case, the sum space of the RKHSs is isomorphic to the product space and hence the proposed algorithm can also be regarded as an iterative projection method in the sum space. The efficacy of the proposed algorithm is shown by numerical examples.
△ Less
Submitted 4 November, 2014; v1 submitted 4 August, 2014;
originally announced August 2014.
-
Kernel-Based Adaptive Online Reconstruction of Coverage Maps With Side Information
Authors:
Martin Kasparick,
Renato L. G. Cavalcante,
Stefan Valentin,
Slawomir Stanczak,
Masahiro Yukawa
Abstract:
In this paper, we address the problem of reconstructing coverage maps from path-loss measurements in cellular networks. We propose and evaluate two kernel-based adaptive online algorithms as an alternative to typical offline methods. The proposed algorithms are application-tailored extensions of powerful iterative methods such as the adaptive projected subgradient method and a state-of-the-art ada…
▽ More
In this paper, we address the problem of reconstructing coverage maps from path-loss measurements in cellular networks. We propose and evaluate two kernel-based adaptive online algorithms as an alternative to typical offline methods. The proposed algorithms are application-tailored extensions of powerful iterative methods such as the adaptive projected subgradient method and a state-of-the-art adaptive multikernel method. Assuming that the moving trajectories of users are available, it is shown how side information can be incorporated in the algorithms to improve their convergence performance and the quality of the estimation. The complexity is significantly reduced by imposing sparsity-awareness in the sense that the algorithms exploit the compressibility of the measurement data to reduce the amount of data which is saved and processed. Finally, we present extensive simulations based on realistic data to show that our algorithms provide fast, robust estimates of coverage maps in real-world scenarios. Envisioned applications include path-loss prediction along trajectories of mobile users as a building block for anticipatory buffering or traffic offloading.
△ Less
Submitted 10 October, 2019; v1 submitted 3 April, 2014;
originally announced April 2014.
-
Robust Reduced-Rank Adaptive Processing Based on Parallel Subgradient Projection and Krylov Subspace Techniques
Authors:
R. C. de Lamare,
M. Yukawa,
I. Yamada
Abstract:
In this paper, we propose a novel reduced-rank adaptive filtering algorithm by blending the idea of the Krylov subspace methods with the set-theoretic adaptive filtering framework. Unlike the existing Krylov-subspace-based reduced-rank methods, the proposed algorithm tracks the optimal point in the sense of minimizing the \sinq{true} mean square error (MSE) in the Krylov subspace, even when the es…
▽ More
In this paper, we propose a novel reduced-rank adaptive filtering algorithm by blending the idea of the Krylov subspace methods with the set-theoretic adaptive filtering framework. Unlike the existing Krylov-subspace-based reduced-rank methods, the proposed algorithm tracks the optimal point in the sense of minimizing the \sinq{true} mean square error (MSE) in the Krylov subspace, even when the estimated statistics become erroneous (e.g., due to sudden changes of environments). Therefore, compared with those existing methods, the proposed algorithm is more suited to adaptive filtering applications. The algorithm is analyzed based on a modified version of the adaptive projected subgradient method (APSM). Numerical examples demonstrate that the proposed algorithm enjoys better tracking performance than the existing methods for the interference suppression problem in code-division multiple-access (CDMA) systems as well as for simple system identification problems.
△ Less
Submitted 26 June, 2013;
originally announced June 2013.
-
Lp-Regularized Least Squares (0<p<1) and Critical Path
Authors:
Masahiro Yukawa,
Shun-ichi Amari
Abstract:
The least squares problem is formulated in terms of Lp quasi-norm regularization (0<p<1). Two formulations are considered: (i) an Lp-constrained optimization and (ii) an Lp-penalized (unconstrained) optimization. Due to the nonconvexity of the Lp quasi-norm, the solution paths of the regularized least squares problem are not ensured to be continuous. A critical path, which is a maximal continuous…
▽ More
The least squares problem is formulated in terms of Lp quasi-norm regularization (0<p<1). Two formulations are considered: (i) an Lp-constrained optimization and (ii) an Lp-penalized (unconstrained) optimization. Due to the nonconvexity of the Lp quasi-norm, the solution paths of the regularized least squares problem are not ensured to be continuous. A critical path, which is a maximal continuous curve consisting of critical points, is therefore considered separately. The critical paths are piecewise smooth, as can be seen from the viewpoint of the variational method, and generally contain non-optimal points such as saddle points and local maxima as well as global/local minima. Along each critical path, the correspondence between the regularization parameters (which govern the 'strength' of regularization in the two formulations) is non-monotonic and, more specifically, it has multiplicity. Two paths of critical points connecting the origin and an ordinary least squares (OLS) solution are highlighted. One is a main path starting at an OLS solution, and the other is a greedy path starting at the origin. Part of the greedy path can be constructed with a generalized Minkowskian gradient. The breakpoints of the greedy path coincide with the step-by-step solutions generated by using orthogonal matching pursuit (OMP), thereby establishing a direct link between OMP and Lp-regularized least squares.
△ Less
Submitted 24 April, 2013;
originally announced April 2013.
-
Coordinated Beamforming with Relaxed Zero Forcing: The Sequential Orthogonal Projection Combining Method and Rate Control
Authors:
Juho Park,
Gilwon Lee,
Youngchul Sung,
Masahiro Yukawa
Abstract:
In this paper, coordinated beamforming based on relaxed zero forcing (RZF) for K transmitter-receiver pair multiple-input single-output (MISO) and multiple-input multiple-output (MIMO) interference channels is considered. In the RZF coordinated beamforming, conventional zero-forcing interference leakage constraints are relaxed so that some predetermined interference leakage to undesired receivers…
▽ More
In this paper, coordinated beamforming based on relaxed zero forcing (RZF) for K transmitter-receiver pair multiple-input single-output (MISO) and multiple-input multiple-output (MIMO) interference channels is considered. In the RZF coordinated beamforming, conventional zero-forcing interference leakage constraints are relaxed so that some predetermined interference leakage to undesired receivers is allowed in order to increase the beam design space for larger rates than those of the zero-forcing (ZF) scheme or to make beam design feasible when ZF is impossible. In the MISO case, it is shown that the rate-maximizing beam vector under the RZF framework for a given set of interference leakage levels can be obtained by sequential orthogonal projection combining (SOPC). Based on this, exact and approximate closed-form solutions are provided in two-user and three-user cases, respectively, and an efficient beam design algorithm for RZF coordinated beamforming is provided in general cases. Furthermore, the rate control problem under the RZF framework is considered. A centralized approach and a distributed heuristic approach are proposed to control the position of the designed rate-tuple in the achievable rate region. Finally, the RZF framework is extended to MIMO interference channels by deriving a new lower bound on the rate of each user.
△ Less
Submitted 2 October, 2012; v1 submitted 8 March, 2012;
originally announced March 2012.