PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Sparse System Identification and Signal Reconstruction using Projections onto Weighted $\ell_1$ Balls

Yannis Kopsinis, Konstantinos Slavakis, Sergios Theodoridis

arXiv:1004.3040v1cs.IT

TL;DR

The paper addresses online sparse signal and system estimation when batch methods cannot adapt to incoming measurements or time variation. It proposes projections onto measurement-derived hyperslabs and weighted ℓ1 balls, and reports an efficient algorithm evaluated in time-invariant and time-varying settings.

  • Problem

    The problem is to estimate sparse signals or systems online while tracking possible time variation under affordable computational complexity.

  • Method

    The method projects sequentially onto hyperslabs generated from measurements and weighted ℓ1 balls that impose sparsity.

  • Results

    The proposed algorithm is evaluated against existing methods using simulated data in time-invariant and time-varying scenarios.

  • Takeaways & Limitations

    The paper presents a linear-complexity adaptive approach for sparse system identification based on hyperslab and weighted-ℓ1-ball projections.

  • Takeaways & Limitations

    The paper notes that a different parameter setup could yield faster convergence for both LMS-based methods.

Abstract

from arXiv · show

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_2L)$ 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.

1. Introduction

The paper targets online sparse signal and system estimation, where batch compressed-sensing methods cannot update estimates as measurements arrive. It introduces a projection-based adaptive scheme using hyperslabs and weighted ℓ1 balls, with stated low computational complexity.

  • Batch compressed-sensing methods require a predefined number of measurements before processing and cannot update estimates dynamically as new data arrive.
  • The paper develops a projection-based algorithm for sparse system identification and sparse signal reconstruction.
  • Each new measurement generates a closed convex hyperslab representing solutions in agreement with the current data.
  • The algorithm imposes sparsity through exact projections onto weighted ℓ1 balls rather than subgradient information.
  • O(qL) multiplications/additions and O(L log2 L) sorting operations characterize the stated computational complexity.
  • The paper evaluates the proposed scheme in time-invariant and time-varying scenarios and discusses convergence theory that extends existing results.

2. Problem description

The paper formulates sparse signal reconstruction and sparse system identification as online estimation problems for a sparse unknown vector. Unlike batch methods, the estimator must track time variation while retaining fast convergence and affordable complexity.

  • The unknown vector h∗ is S-sparse, with S nonzero terms much smaller than the signal or system length L.
  • Sparse signal reconstruction estimates h∗ from inner-product measurements obtained using selected input vectors.
  • Sparse system identification estimates an unknown impulse response from outputs generated by probing the system with an input signal.
  • LASSO is presented as a batch method requiring the complete measurement count N before solving its task.
  • The study allows h∗ to vary over time, requiring estimates to track changes as measurements arrive.
  • The desired online techniques should exploit sparsity, approach batch error floors quickly, track well, and maintain low computational demands.

3. Online estimation under the sparsity constraint

The paper contrasts recursive loss minimization with a set-theoretic online approach. Its estimates are constrained by measurement-consistent hyperslabs and weighted ℓ1 balls, then updated through projections.

  • Online estimation generates a sequence of estimates intended to converge toward a value that best approximates the unknown sparse vector.
  • The set-theoretic approach seeks solutions satisfying observations and constraints instead of recursively minimizing a cost over all observations.
  • A hyperslab is a closed convex property set whose points agree with the corresponding measurement within a user-defined tolerance.
  • The hyperslab intersection may be nonempty, while the convergence analysis also allows finitely many property sets not to intersect the rest.
  • Sparsity is represented by a weighted ℓ1 ball, also a closed convex set, and estimates are sought in its intersection with the hyperslabs.
  • Time-dependent weights are used for additional flexibility and are stated to speed convergence and decrease misadjustment error.

4. Proposed algorithmic framework

The framework updates an estimate by projecting onto data-defined hyperslabs, combining those projections, and enforcing sparsity through a time-varying weighted ℓ1-ball projection. The resulting scheme supports sliding-window updates, concurrent hyperslab projections, and computational costs that scale linearly with system order apart from sorting.

  • Each new data pair forms a hyperslab, and previously formed hyperslabs may also be retained in a sliding window.
  • Each update projects the current estimate onto selected hyperslabs, combines the projections, and projects the result onto the weighted ℓ1 ball.
  • The algorithm uses metric projections onto both hyperslabs and the currently available weighted ℓ1 ball.
  • O(qL) multiplications/additions and O(L log_2 L) sorting operations characterize the computational load, with q-dependence relaxed under parallel processing.
  • The weighted-ball projection is time-varying and depends on the obtained estimates, requiring convergence analysis beyond the unweighted case.

5. Projections onto Closed Convex Sets

The paper formulates projection operations for closed convex constraints and derives an exact finite-step projection onto weighted ℓ1 balls. The weighted-ball procedure sorts normalized magnitudes, identifies the active coordinates, and restores their original signs and positions.

  • For a closed convex set, the metric projection uniquely maps a point to the closest point in that set.
  • The hyperslab projection has a simple analytic form based on the data pair, the tolerance width, and the current estimate.
  • The final projected vector restores the original coordinate order and signs after projection in the non-negative hyperoctant.
  • The weighted ℓ1-ball projection can be computed exactly in at most L recursive steps.
  • The procedure sorts |h_i|/w_i in non-ascending order, determines the active coordinates, and fills the remaining coordinates with zeros.

6. Weighting the ℓ1 Ball

The method designs adaptive weights for a weighted ℓ1 constraint and names the resulting algorithm APWL1. The radius is tied to the estimated sparsity level rather than the unweighted ℓ1 norm of the unknown system.

  • The weight sequence uses small positive parameters to avoid division by zero when forming componentwise weights.
  • The weighted algorithm is called Adaptive Projection Algorithm onto Weighted ℓ1 balls (APWL1), while the unweighted variant is called APL1.
  • In the weighted case, the constraint radius is set to S = ∥h*∥_ℓ0 rather than δ = ∥h*∥_ℓ1.
  • If the estimates converge to h*, the weighted constraint is eventually justified because h_n belongs to B_ℓ1[w_n, ∥h*∥_ℓ0].

7. Convergence Properties of the Algorithm

Under stated convexity, intersection, and weighting assumptions, the algorithm converges toward the intersection of the active hyperslabs and weighted ℓ1 balls. The convergence guarantee tolerates a finite number of inconsistent constraint sets, so finite data outliers do not disturb convergence.

  • The convergence result allows a finite number of closed convex sets to lack a nonempty intersection with the remaining constraints.
  • Finite data outliers therefore do not disturb the algorithm's convergence under the stated conditions.
  • Under the adopted assumptions, the convergence theorem establishes monotonic progress toward the intersection Ω.
  • The distances of the estimates from the corresponding hyperslabs and weighted ℓ1 balls tend asymptotically to zero.
  • The estimate sequence converges to a point in, or arbitrarily close to, an intersection of the involved constraint sets.
  • In the sparse identification example, APWL1 exhibits the best performance in the high-noise comparison, while its improvement is also reported at low noise.

8. Performance evaluation

The evaluation compares the proposed projection-based algorithms with LMS-, LASSO-, and RLASSO-based methods across time-invariant, signal-reconstruction, and time-varying sparse-system tasks. APWL1 generally improves convergence and steady-state performance, while its complexity increases with q but remains below RLASSO in the reported example.

  • Evaluation setup: The experiments use ensemble averages over 100 independent runs and compare the proposed methods with ZA-LMS, RZA-LMS, RLASSO, and batch LASSO.Batch LASSO provides a benchmark for ℓ1-regularized least-squares solvers.
  • Time-invariant case: APWL1 achieves the best convergence speed and steady-state error floor in the time-invariant comparison, whereas unweighted APL1 has higher error floors.Increasing q accelerates convergence, while APL1 performs worse than both LMS-based methods in the cited comparison.
  • Time-invariant case: At low noise, APWL1’s performance advantage over LMS-based algorithms becomes more pronounced, at the expense of higher complexity.The LMS-based algorithms require O(L) multiply/add operations, while APWL1 requires more operations as q increases.
  • Time-invariant case: Convergence speed improves rapidly as q increases, with the largest improvement occurring at small q values and low noise levels.For large q, APWL1 approaches LASSO and RLASSO performance; q = 60 remains less complex than RLASSO in the reported example.
  • Time-varying case: In the time-varying system experiment, the proposed method outperforms the other methods through time instance 500, while RLASSO trades faster tracking for a higher error floor.With β = 0.8, RLASSO improves tracking speed but has a significantly increased error floor; with β = 0.9, it matches the proposed tracking speed but retains a higher floor.

9. Sensitivity of APWL1 to Non ideal Parameter Setting

The section compares APWL1, LASSO, and LMS-based methods under parameter deviations from optimized settings. APWL1 is highly sensitive to underestimation of δ but relatively tolerant of overestimation, while LASSO is particularly sensitive to δ deviations.

  • Sensitivity to δ: APWL1 achieves its best performance when δ equals the true value S.The section identifies the solid curve with squares as the best-performing APWL1 configuration.
  • Sensitivity to δ: A 10% underestimation of δ causes significant APWL1 performance degradation.By contrast, overestimating δ by 100% still produces acceptable performance.
  • Comparison with LASSO: LASSO is more sensitive to δ than APWL1, with a 25% deviation from the optimum moving it into a higher MSE regime.The comparison uses the optimized LASSO value δ = ∥h∗∥ℓ1.
  • Sensitivity to ǫ, µ, and ρ: APWL1 has very low sensitivity to positive deviations in ǫ, whereas slight underestimation causes sudden performance degradation.The section compares this behavior with the sensitivity of LMS-based methods to ρ.
  • Sensitivity to ǫ, µ, and ρ: LMS-based methods are more sensitive to µ deviations, and their optimum µ depends on the length of h∗.This dependence is also reported for standard non-regularized LMS.

10. Conclusions

The conclusions present a linear-complexity sparse system identification algorithm based on set-theoretic estimation. It uses projections onto hyperslabs and weighted ℓ1 balls, includes a convergence proof, and is compared with online sparse LMS- and LS-type methods.

  • Contributions: The proposed algorithm is a novel efficient method with linear complexity for sparse adaptive system identification.Its design is based on set-theoretic estimation arguments.
  • Contributions: Sparsity is imposed through a sequence of weighted ℓ1 balls.The weighted balls are part of the algorithm's set-theoretic construction.
  • Algorithm: The algorithm alternates projections onto hyperslabs that measure data mismatch and onto weighted ℓ1 balls.The hyperslabs are generated from the observed training data.
  • Theory: The weighted ℓ1-ball projection mapping is derived and a full convergence proof is established.
  • Evaluation: Simulated data are used to compare performance against recently developed online sparse LMS- and sparse LS-type algorithms.

Appendix A. The metric projection mapping onto the weighted ℓ1 ball Bℓ1[w, δ]

The appendix develops the metric projection onto a weighted ℓ1 ball using hyperoctant geometry and convex projection properties. It reduces the projection problem to nonnegative coordinates and supplies lemmas used by the algorithm and convergence analysis.

  • Projection geometry: The weighted ℓ1-ball projection preserves the input vector's hyperoctant.This is stated as the first part of Lemma 1.
  • Projection geometry: The absolute-value mapping bijectively maps each hyperoctant onto the nonnegative hyperoctant.This reduction lets the projection be studied using nonnegative coordinates.
  • Algorithmic formulation: The algorithm is equivalently expressed using convex functions formed from distances to hyperslabs and relaxed subgradient projections.The extrapolation parameter is allowed to take values greater than or equal to 2 through the introduced scaling.
  • Convergence tools: The convergence analysis relies on bounded subgradients of the distance functions and standard properties of metric and subgradient projections.

B.2. The proof of Theorem 2.

The proof establishes convergence by showing boundedness, asymptotic feasibility with respect to the hyperslabs, and convergence of distances to points in the solution set. Under stronger assumptions, the iterate sequence has a unique cluster point and converges.

  • Boundedness and feasibility: The sequence of distances from the iterates to any solution point is shown to converge.The proof uses monotonicity and lower boundedness of the distance sequence.
  • Asymptotic feasibility: The proof shows that the residual function Θn(hn) tends to zero, establishing asymptotic satisfaction of the hyperslab constraints.
  • Boundedness and feasibility: The proof first establishes that the iterate sequence is bounded under the stated assumptions.A uniform bound D is constructed from an initial iterate and a point in the solution set.
  • Convergence: If the relevant assumptions hold, the iterates converge to a unique cluster point.This follows by combining the convergence inequality with the existence of a unique cluster point.
  • Asymptotic feasibility: The contradiction argument rules out a persistent positive maximum distance from the generated hyperslabs.Such persistence would contradict the previously established vanishing residual result.
Loading 1004.3040v1…