Source-linked AI summary
Sparse Recovery of Streaming Signals Using L1-Homotopy
M. Salman Asif, Justin Romberg
TL;DR
The paper tackles sparse recovery when signals, measurements, and representations evolve over overlapping streaming intervals. It uses sliding-interval weighted ℓ1 minimization with warm-start homotopy updates for smooth LOT-represented signals and linearly dynamic signals. Experiments report better reconstruction quality than independent block methods and lower computation time and complexity than state-of-the-art solvers.
Problem
Static sparse-recovery frameworks are not readily applicable when an unknown signal changes over time and is measured and reconstructed sequentially over short intervals.
Method
The paper processes measurements over sliding intervals, solves weighted ℓ1 problems for sparse coefficients, and uses available estimates as warm starts for homotopy updates.
Results
The streaming recovery framework outperforms independent disjoint-block reconstruction in reconstruction quality, while homotopy updating outperforms current state-of-the-art solvers in computation time and complexity.
Takeaways & Limitations
The proposed homotopy algorithm supports recovery for smooth LOT-based signals and sparse signals following linear dynamic models while adapting as the streaming system changes.
Abstract
from arXiv · showhide
Most of the existing methods for sparse signal recovery assume a static system: the unknown signal is a finite-length vector for which a fixed set of linear measurements and a sparse representation basis are available and an L1-norm minimization program is solved for the reconstruction. However, the same representation and reconstruction framework is not readily applicable in a streaming system: the unknown signal changes over time, and it is measured and reconstructed sequentially over small time intervals. In this paper, we discuss two such streaming systems and a homotopy-based algorithm for quickly solving the associated L1-norm minimization programs: 1) Recovery of a smooth, time-varying signal for which, instead of using block transforms, we use lapped orthogonal transforms for sparse representation. 2) Recovery of a sparse, time-varying signal that follows a linear dynamic model. For both the systems, we iteratively process measurements over a sliding interval and estimate sparse coefficients by solving a weighted L1-norm minimization program. Instead of solving a new L1 program from scratch at every iteration, we use an available signal estimate as a starting point in a homotopy formulation. Starting with a warm-start vector, our homotopy algorithm updates the solution in a small number of computationally inexpensive steps as the system changes. The homotopy algorithm presented in this paper is highly versatile as it can update the solution for the L1 problem in a number of dynamical settings. We demonstrate with numerical experiments that our proposed streaming recovery framework outperforms the methods that represent and reconstruct a signal as independent, disjoint blocks, in terms of quality of reconstruction, and that our proposed homotopy-based updating scheme outperforms current state-of-the-art solvers in terms of the computation time and complexity.
I. INTRODUCTION
The paper addresses sparse recovery for streaming signals whose measurements or representations overlap across shifting intervals, rather than treating each block independently. It develops sliding-interval weighted ℓ1 recovery and homotopy updates for smooth signals with LOT representations and signals governed by linear dynamics.
- Motivation: Static sparse-recovery methods do not directly fit streaming signals that vary over time and lack clear beginnings and ends.The paper focuses on estimating signals from incomplete measurements collected over short, shifting intervals.
- Overlapping systems: Independent block reconstruction is suboptimal when measurement or representation systems overlap across adjacent signal intervals.Overlapping systems arise through Φt, Ψt, or both, including LOT-based representations.
- Target systems: The paper covers smooth time-varying signals using compactly supported overlapping bases and time-varying signals coupled by a linear dynamic model.For the dynamic model, prediction errors are assumed to have bounded ℓ2 norm.
- Streaming recovery: The framework jointly processes measurements over sliding active intervals and estimates sparse coefficients with weighted ℓ1 minimization.Each iteration builds an active-interval model, solves for coefficients, then removes old measurements and adds new ones.
- Homotopy updating: Available estimates update the sparsity weights and initialize the next optimization, avoiding a new solution from scratch at every iteration.The previous estimate is used as a warm start for the homotopy formulation.
- Algorithmic contribution: The proposed homotopy algorithm updates weighted ℓ1 solutions under changes in measurements, measurement matrices, representation matrices, and weights.Unlike prior approaches described here, it permits an arbitrary warm-start vector, although closer starts update faster.
II. SIGNAL REPRESENTATION USING COMPACTLY SUPPORTED BASES
The paper represents streaming signals with compactly supported orthogonal bases whose supports overlap, emphasizing LOTs to avoid boundary discontinuities introduced by disjoint block transforms.
- Lapped orthogonal transforms: LOT represents a discrete-time signal using orthogonal components with compact, overlapping supports and sparse or compressible coefficients.Its basis functions use smooth windows and cosine-IV functions, with orthogonality maintained across overlaps.
- Motivation: Block-based cosine or Fourier transforms can introduce artificial boundary discontinuities that damage sparsity, motivating lapped transforms.LOTs replace rectangular windows with smooth overlapping windows.
- Lapped orthogonal transforms: LOT intervals overlap at neighboring boundaries, and the corresponding synthesis matrices share rows while preserving an orthogonal basis structure.The overlapping components are summed to synthesize the signal over the active interval.
- Active-interval representation: Over an active interval, the representation stacks coefficients from every basis interval that overlaps the interval and combines their restricted synthesis matrices.Adjacent synthesis matrices overlap in rows, so boundary components contribute jointly to the represented signal.
- Related bases: Wavelet bases provide another compact, overlapping orthogonal representation, with components overlapping across adjacent blocks and resolutions.The paper uses LOTs in most explanations while retaining a general lapped-basis framework.
III. SPARSE SIGNAL RECOVERY FROM STREAMING MEASUREMENTS
The streaming recovery framework estimates sparse coefficients over a sliding active interval, updating measurements and representations as new signal portions arrive.
- Streaming framework: The system repeatedly estimates sparse coefficients and the signal over an active, sliding interval using streaming measurements.Measurements entering and leaving the interval are processed sequentially rather than reconstructing the entire signal at once.
- Streaming framework: At each iteration, the active interval removes older measurements, adds newer ones, and commits the departing signal portion to the output.The interval length controls delay, memory, and computational complexity.
- System model: The active signal portion is modeled through overlapping measurement blocks and a corresponding overlapping sparse representation.The stacked system contains the relevant measurement matrices, noise, basis coefficients, and synthesis matrices.
- Problem settings: The framework covers two cases: signals represented with lapped orthogonal bases and signals evolving according to a linear dynamic model.These cases are treated as distinct streaming recovery problems.
A. Streaming signal with lapped orthogonal bases
For lapped orthogonal representations, recovery must account for overlapping coefficient supports when the active interval advances and previously committed coefficients are removed.
- Coefficient removal: Because overlapping columns couple variables, removing an old coefficient vector requires removing corresponding columns rather than simply deleting rows.This differs from the block-diagonal case, where independent variables and rows could be removed directly.
- Active-interval design: The lapped representation includes every coefficient vector whose basis interval partially or fully overlaps the active interval.The design seeks to keep the number of unknown coefficients in the active system small.
- Coefficient removal: The system is divided into committed and unknown components, and the estimated contribution of the committed component is subtracted from the measurements.The remaining unknown coefficients are then estimated from a modified system.
- Recovery problem: The unknown coefficients are recovered by solving a weighted ℓ1-norm minimization problem on the modified overlapping system.The modified measurement vector includes the effect of the estimated committed coefficients through a combined error term.
2) Recovery problem:
The recovery procedure uses prior coefficient estimates to warm-start weighted ℓ1 recovery and incorporates linear prediction equations for dynamically evolving signals.
- Warm-start recovery: Positive diagonal weights are selected using prior information about the previous coefficient estimate to guide weighted ℓ1 recovery.The prior estimate is expected to be close to the current solution because consecutive active intervals substantially overlap.
- Warm-start recovery: Instead of solving each weighted ℓ1 problem from scratch, the previous estimate is supplied as a warm-start vector to the solver.The signal estimate and available measurements are used to construct the prior coefficient estimate.
- New coefficients: New coefficient values are predicted from the previous signal estimate using extension, support identification, restricted least squares, and thresholding.The described procedure uses symmetric extension to populate new locations before estimating their magnitudes.
- Linear dynamic model: For a linear dynamic model, prediction equations are appended to the measurement system and stacked into a banded matrix.The combined system includes prediction errors and the predicted contribution of the coefficient vector removed from the active interval.
- Linear dynamic model: The dynamic-model matrix places negative identity matrices on the main diagonal and transition matrices below it.The resulting system jointly represents measurements, sparse synthesis, and temporal prediction.
2) Recovery problem:
The recovery problem combines sparse representation with a dynamic-model penalty and uses warm starts to update weighted ℓ1 solutions as streaming systems change. A homotopy path moves from an available initial estimate to the target solution through inexpensive support updates.
- Recovery formulation: The objective combines weighted ℓ1 sparsity, measurement fidelity, and a regularization term that incorporates the dynamic model.The parameter λ controls the dynamic model's effect on the solution.
- Recovery formulation: Prior coefficient estimates determine the weights and warm start, with new coefficients predicted from the previous signal estimate.The incoming signal portion is predicted using the dynamic model before updating coefficients and weights.
- Homotopy update: The homotopy algorithm starts from an available estimate and continuously transforms an auxiliary problem into the target ℓ1 problem.The solution follows a piece-wise linear path as the homotopy parameter changes from 0 to 1.
- Scope: The method dynamically updates ℓ1 solutions for streaming recovery and can accommodate changing measurements and warm-start vectors.Its stated computational structure uses inexpensive steps while updating the solution as the system changes.
- Homotopy update: Each homotopy step updates the solution direction and changes the support when a constraint becomes active or a coefficient reaches zero.The procedure repeats these updates until the homotopy parameter equals 1.
V. NUMERICAL EXPERIMENTS
The experiments evaluate streaming recovery for two types of time-varying signals and compare the proposed homotopy solver with state-of-the-art ℓ1 solvers across compression factors. The reported comparison emphasizes reconstruction performance and computational cost.
- Experimental scope: The experiments study signals sparse in LOT bases and signals following a linear dynamic model with sparse wavelet representations.Both signal types are recovered from streaming compressive measurements.
- Experimental scope: The study evaluates the proposed recovery algorithms at different compression factors.This varies the measurement-compression setting used in the streaming experiments.
- Solver comparison: The ℓ1-homotopy algorithm is compared with two state-of-the-art ℓ1 solvers.The comparison concerns computational requirements in the same streaming recovery setting.
- Solver comparison: ℓ1-homotopy requires significantly fewer computational operations than the comparison solvers.The passage reports this computational advantage for the experiments described.
A. Signals with LOT representation
The LOT experiment uses streaming signals whose sparse representations are formed in lapped orthogonal transform bases.
- Signal selection: The LOT experiment evaluates two discrete-time signals from the Wavelab toolbox that have sparse representations in LOT bases.The passage introduces the signal set used for this experiment.
1) Experiment setup:
The experiment setup constructs noisy streaming compressive measurements, represents signals with overlapping LOT intervals, and compares warm-started ℓ1-homotopy with YALL1 and SpaRSA. Reconstruction quality and computational cost are measured under matched initialization and weighting procedures.
- Signals: The LOT test signals are LinChirp and MishMash, with their LOT coefficients used for sparse streaming recovery.LinChirp is a critically sampled sinusoidal chirp, while MishMash combines quadratic and linear chirps with increasing frequencies and a sinusoid.
- Measurement setup: Measurements are generated from non-overlapping signal blocks with M = N/R measurements at compression rate R and Gaussian noise selected for 35 dB expected SNR.The measurement matrices are generated independently at random.
- Representation: LOT coefficients are computed on overlapping intervals of length 2N with overlap parameter ηp = N/2.The signal is divided into overlapping intervals before transform coefficients are computed.
- Streaming procedure: Each streaming iteration builds a joint system for P = 5 consecutive blocks, shifts the active interval, and updates measurements and coefficients.The previous solution supplies predicted coefficients and a warm start for the weighted ℓ1 problem.
- Solver comparison: The proposed solver is compared with YALL1 and SpaRSA using identical initialization and weight-selection procedures.Both comparison solvers use previous-iteration solutions to initialize the next streaming iteration.
- Evaluation: Evaluation records signal-to-error ratio, matrix-vector products involving A and A^T, and MATLAB execution time.All algorithms are run in MATLAB on a standard laptop using a single computational thread.
B. Results
Experiments on LinChirp and MishMash compare LOT-based streaming reconstruction with block-transform reconstruction and evaluate three ℓ1 solvers. LOT provides better reconstruction quality than DCT, while ℓ1-homotopy achieves comparable error with lower computational cost and execution time.
- ℓ1-homotopy, SpaRSA, and YALL1 produced almost identical SER because they solve the same convex program.
- More than 20 dB loss in SER occurred with DCT-based representation compared with LOT-based representation.
- ℓ1-homotopy required the fewest A^T A applications among the three solvers in all experiments.The computational cost was measured by counting matrix-vector multiplications.
- ℓ1-homotopy consumed distinctly less reconstruction time than YALL1 and SpaRSA.
- MishMash experiments likewise found nearly identical reconstruction error across solvers, but lower computational cost and execution time for ℓ1-homotopy.
- Across the experiments, LOT-based reconstruction had significantly better quality than DCT-based reconstruction, while ℓ1-homotopy had lower computational cost and execution time than SpaRSA and YALL1.
C. Linear dynamic model
The linear-dynamic-model experiments generate time-varying signals through shifted instances and reconstruct them from streaming compressive measurements using sparse wavelet coefficients. A sliding system is updated with predicted coefficients and solved using a warm-started weighted ℓ1 method.
- The simulated time-varying signal follows x_t+1 = F_t x_t + f_t and is built from successive signal instances.
- HeaviSine and Piece-Regular serve as seed signals, with shifted copies forming the streaming sequence.
- The experiments use streaming compressive measurements with M = N/R measurements and Gaussian noise targeting an expected SNR of 35 dB.
- At each iteration, the active interval shifts, old measurements are removed, new measurements are added, and part of the estimated coefficient vector is committed to the output.
- YALL1 is excluded from these experiments because it only works with under-determined systems.
2) Results:
For HeaviSine and Piece-Regular signals, combining a linear dynamic model with ℓ1 regularization improves reconstruction relative to Kalman filtering or ℓ1 regularization alone. ℓ1-homotopy matches SpaRSA’s reconstruction quality while requiring less computation and time.
- ℓ1-homotopy and SpaRSA achieved almost identical reconstruction error because both solve the same convex program.
- The ℓ1-regularized solution outperformed the LS-Kalman estimate, while omitting the dynamic model caused significant degradation and results inferior to LS-Kalman.
- ℓ1-homotopy used fewer matrix-vector multiplications and less computation time than the alternatives for HeaviSine reconstruction.
- Piece-Regular experiments similarly found nearly identical reconstruction error for ℓ1-homotopy and SpaRSA, with better computational cost and execution time for ℓ1-homotopy.
- Combining a linear dynamic model with ℓ1-norm regularization provided much better reconstruction than Kalman filtering or ℓ1-regularized problems alone.
- The average update required 3 to 10 homotopy steps and 5 to 13 milliseconds across 128 iterations.