Discrete and Continuous-time Soft-Thresholding with Dynamic Inputs
arXiv:1405.1361 · doi:10.1109/TSP.2015.2420535
Abstract
There exist many well-established techniques to recover sparse signals from compressed measurements with known performance guarantees in the static case. However, only a few methods have been proposed to tackle the recovery of time-varying signals, and even fewer benefit from a theoretical analysis. In this paper, we study the capacity of the Iterative Soft-Thresholding Algorithm (ISTA) and its continuous-time analogue the Locally Competitive Algorithm (LCA) to perform this tracking in real time. ISTA is a well-known digital solver for static sparse recovery, whose iteration is a first-order discretization of the LCA differential equation. Our analysis shows that the outputs of both algorithms can track a time-varying signal while compressed measurements are streaming, even when no convergence criterion is imposed at each time step. The L2-distance between the target signal and the outputs of both discrete- and continuous-time solvers is shown to decay to a bound that is essentially optimal. Our analyses is supported by simulations on both synthetic and real data.
arXiv comment18 pages, 7 figures, journal
References in corpus (8)
- Kalman Filtered Compressed Sensing
- Linear convergence of iterative soft-thresholding
- Some sharp performance bounds for least squares regression with regularization
- Dynamic Updating for L1 Minimization
- Convergence and Rate Analysis of Neural Networks for Sparse Approximation
- A variational Bayes framework for sparse adaptive estimation
- Convergence Speed of a Dynamical System for Sparse Recovery
- Compressive Sampling for Networked Feedback Control
Cited by in corpus (6)
- Prediction-Correction Algorithms for Time-Varying Constrained Optimization
- Dynamic Filtering of Time-Varying Sparse Signals via l1 Minimization
- CAPPA: Continuous-time Accelerated Proximal Point Algorithm for Sparse Recovery
- Extrapolation-based Prediction-Correction Methods for Time-varying Convex Optimization
- Escaping spurious local minimum trajectories in online time-varying nonconvex optimization
- WARP-LCA: Efficient Convolutional Sparse Coding with Locally Competitive Algorithm