Online Sparse System Identification and Signal Reconstruction using Projections onto Weighted ${\ell }_1$ Balls

Abstract

This paper presents a novel projection-based adaptive algorithm for sparse signal and system identification. The sequentially observed data are used to generate an equivalent sequence of closed convex sets, namely hyperslabs. Each hyperslab is the geometric equivalent of a cost criterion, that quantifies "data mismatch". Sparsity is imposed by the introduction of appropriately designed weighted ${\ell }_1$ balls. The algorithm develops around projections onto the sequence of the generated hyperslabs as well as the weighted ${\ell }_1$ balls. The resulting scheme exhibits linear dependence, with respect to the unknown system's order, on the number of multiplications/additions and an $\mathcal{O}(L{\log }_{2}L)$ dependence on sorting operations, where $L$ is the length of the system/signal to be estimated. Numerical results are also given to validate the performance of the proposed method against the LASSO algorithm and two very recently developed adaptive sparse LMS and LS-type of adaptive algorithms, which are considered to belong to the same algorithmic family.

Extented version of preprint submitted to IEEE trans. on Signal Processing

Cited by in corpus (27)

• Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
• Sparse Distributed Learning Based on Diffusion Adaptation
• Performance Analysis of l_0 Norm Constraint Least Mean Square Algorithm
• A Survey of Stochastic Simulation and Optimization Methods in Signal Processing
• Combinations of Adaptive Filters
• Adaptive Least Mean Squares Estimation of Graph Signals
• A Sparsity-Aware Adaptive Algorithm for Distributed Learning
• Kernel-Based Structural Equation Models for Topology Identification of Directed Networks
• Recursive Recovery of Sparse Signal Sequences from Compressive Measurements: A Review
• Regularized Least-Mean-Square Algorithms
• Proximal Multitask Learning over Networks with Sparsity-inducing Coregularization
• A variational Bayes framework for sparse adaptive estimation
• Online Hyperparameter-Free Sparse Estimation Method
• Nonlinear Structural Vector Autoregressive Models for Inferring Effective Brain Network Connectivity
• Diffusion Adaptation Strategies for Distributed Estimation over Gaussian Markov Random Fields
• An Online Parallel and Distributed Algorithm for Recursive Estimation of Sparse Signals
• CEBoosting: Online Sparse Identification of Dynamical Systems with Regime Switching by Causation Entropy Boosting
• The adaptive projected subgradient method constrained by families of quasi-nonexpansive mappings and its application to online learning
• Uncertainty Principle and Sparse Reconstruction in Pairs of Orthonormal Rational Function Bases
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization
• Performance Limits of Stochastic Sub-Gradient Learning, Part II: Multi-Agent Case
• Dynamic mode decomposition for compressive system identification
• A Stochastic Majorize-Minimize Subspace Algorithm for Online Penalized Least Squares Estimation
• Efficient Projection Algorithms onto the Weighted l1 Ball
• Sparse System Identification for Stochastic Feedback Control Systems
• Low-Complexity Set-Membership Normalized LMS Algorithm for Sparse System Modeling
• Generalized Thresholding and Online Sparsity-Aware Learning in a Union of Subspaces