Source-linked AI summary
Theoretical Linear Convergence of Unfolded ISTA and its Practical Weights and Thresholds
Xiaohan Chen, Jialin Liu, Zhangyang Wang, Wotao Yin
TL;DR
The paper addresses the immature theoretical understanding of unfolded ISTA for sparse recovery. It introduces partial weight coupling and support selection, proving linear convergence under the coupling structure and reporting theoretical and empirical acceleration, including real-image compressive sensing results. The conclusions are bounded by assumptions that may fail for non-exactly sparse image codes.
Problem
Unfolded iterative networks perform well empirically, but their theoretical convergence behavior remains insufficiently understood for sparse recovery.
Method
The paper analyzes unfolded ISTA, introduces a partially coupled weight structure, and adds threshold-based support selection.
Results
Linear convergence is established with the proposed weight structure, while support selection improves convergence theoretically and empirically across sparse recovery and image compressive sensing experiments.
Takeaways & Limitations
Weight coupling can reduce trainable parameters without hurting performance, and support selection can further improve practical convergence.
Takeaways & Limitations
The natural-image experiment uses non-exactly sparse codes, so the paper frames it as a robustness demonstration rather than a comparison against all compressive-sensing state-of-the-art methods.
Abstract
from arXiv · showhide
In recent years, unfolding iterative algorithms as neural networks has become an empirical success in solving sparse recovery problems. However, its theoretical understanding is still immature, which prevents us from fully utilizing the power of neural networks. In this work, we study unfolded ISTA (Iterative Shrinkage Thresholding Algorithm) for sparse signal recovery. We introduce a weight structure that is necessary for asymptotic convergence to the true sparse signal. With this structure, unfolded ISTA can attain a linear convergence, which is better than the sublinear convergence of ISTA/FISTA in general cases. Furthermore, we propose to incorporate thresholding in the network to perform support selection, which is easy to implement and able to boost the convergence rate both theoretically and empirically. Extensive simulations, including sparse vector recovery and a compressive sensing experiment on real image data, corroborate our theoretical results and demonstrate their practical usefulness. We have made our codes publicly available: https://github.com/xchen-tamu/linear-lista-cpss.
1 Introduction
The paper studies sparse recovery with unfolded ISTA/LISTA, addressing limited theoretical understanding of why learned networks accelerate iterative solvers. It establishes convergence insights through weight structure and support selection, supported by simulations and image compressive sensing results.
- Problem: Sparse recovery models noisy underdetermined measurements b = Ax∗ + ε, where sparsity makes recovery more tractable.The system has m ≪ n, and the support of x∗ is small compared with n.
- Existing methods: ISTA generally converges sublinearly for fixed dictionary A and sparse code x∗.ISTA applies soft-thresholding with L usually chosen as the largest eigenvalue of A^T A.
- Existing methods: LISTA unrolls ISTA into a K-layer feed-forward network whose parameters are learned using stochastic gradient descent.The architecture includes side connections and learnable weights and thresholds.
- Empirical motivation: Trained LISTA typically reaches ISTA-level accuracy in one or two orders of magnitude fewer iterations while improving across layers.K is usually set to 10–20, and the reported generalization concerns unseen samples from the same distribution.
- Motivations: The paper asks whether parameter dependencies, convergence guarantees, acceleration quantification, and support detection can improve LISTA.These questions target both network simplification and theoretically justified acceleration.
- Contributions: The proposed weight coupling and thresholds yield linear convergence and practical improvements, with simulations and real-image compressive sensing supporting the results.The authors report substantial improvements and superior performance over several state-of-the-art methods in an image compressive sensing task.
2 Algorithm Description
The algorithm description derives a partial coupling of LISTA weights and adds support selection to its thresholding operation. The resulting LISTA-CP, LISTA-SS, and combined LISTA-CPSS variants reduce parameters or accelerate recovery while preserving the intended unfolded structure.
- Partial weight coupling: The paper first establishes a necessary convergence condition that implies partial coupling between LISTA weight matrices.This condition motivates eliminating one weight matrix while retaining trainable layer-dependent parameters.
- Partial weight coupling: Under partial coupling, one weight matrix is shared across layers while the other remains a free parameter to train.The paper adopts this structure for all layers and reports improved performance despite fewer parameters.
- Support selection: Support selection trusts a chosen percentage of largest-magnitude entries as true support and bypasses thresholding for those entries.The selected entries and thresholded entries are both passed into the next layer.
- Support selection: The support-selection percentage p_k is manually controlled, with an empirical schedule p_k = min(p · k, p_max).Both p and p_max are hyperparameters, while θ_k remains trainable.
- Model variants: LISTA-CP uses coupled weights, LISTA-SS uses support selection, and LISTA-CPSS combines both techniques.The paper identifies LISTA-CPSS as the best-performing combined model.
3 Convergence Analysis
The analysis shows that a suitable coupled weight sequence gives unfolded ISTA linear recovery convergence, while adaptive thresholds can improve the convergence–accuracy trade-off. The resulting LISTA-CPSS bounds are at least as good as LISTA-CP and can be strictly better under stronger assumptions.
- Theoretical convergence: ||xk(x∗, ε) − x∗||2 ≤ sB exp(−ck) + Cσ for every layer k, establishing linear convergence toward a noise-dependent error floor.Here c and C depend only on A and s, while s denotes sparsity and σ the noise level.
- Theoretical convergence: The recovery error converges to 0 linearly in the noiseless case, and partial weight coupling is necessary and sufficient for asymptotic convergence.Figure 3 directly validates the corresponding theoretical bounds.
- Convergence trade-offs: ISTA has O(1/k) convergence and FISTA has O(1/k^2) convergence before support stabilization, whereas larger λ trades faster convergence for lower accuracy.After support stabilization, ISTA reduces to a linear iteration; adaptive per-layer thresholds offer a different trade-off.
- Learned parameter sequences: Theorem 2 establishes an existing parameter sequence for LISTA-CP, and experiments show that training can obtain such parameters.In noiseless settings, NMSE converges exponentially to 0; with noise, it converges to a noise-level-dependent stationary value.
- Thresholded support selection: LISTA-CPSS is at least no worse than LISTA-CP and can achieve both a better convergence rate and a smaller approximation error under stronger assumptions.The improved bounds are expressed as ˜c_ss > c and ˜C_ss < C.
4 Numerical Results
Numerical experiments validate the proposed LISTA weight structures and support selection, showing linear convergence and strong recovery performance in sparse and natural-image compressive sensing settings.
- Simulation Experiments: Theorem 1 is directly validated as trained LISTA weights satisfy W^k_2 → I − W^k_1A and θ_k → 0.These quantities are reported to converge as k → ∞ under noiseless training.
- Simulation Experiments: LISTA-CP preserves baseline LISTA’s final performance, outperforms AMP in noiseless and noisy cases, and exhibits exponential NMSE convergence without noise.With noise, NMSE converges to a stationary level related to the noise level.
- Simulation Experiments: LISTA-CPSS converges faster than LISTA-CP in noiseless recovery and achieves lower recovery error in noisy recovery, supporting Theorem 3.The advantage becomes significant for layer counts k ≥ 10, and LISTA-CPSS also outperforms LAMP under the reported conditions.
- Simulation Experiments: As the condition number increases from κ = 5 to 50, LISTA remains stable, LAMP worsens, and LISTA-CPSS remains better than both.The comparison is reported for ill-conditioned matrices with κ = 5, 30, and 50.
- Natural Image Compressive Sensing: The image experiment targets robustness and practical usefulness because natural-image patches are typically not exactly sparse under the learned dictionary.Consequently, the theoretical assumptions do not strictly hold in this non-ideal setting.
- Natural Image Compressive Sensing: In natural-image compressive sensing, LISTA-CPSS is the best performer among the compared methods across CS ratios from 20% to 60%.The experiment uses 16-layer networks and compares TVAL3, Recon-Net, LIHT, LISTA, and LISTA-CPSS on Set 11 images using PSNR.
5 Conclusions
The paper combines partial weight coupling and support selection to make unfolded ISTA more efficient while preserving performance and improving convergence. Simulations and a real-data experiment support these theoretical claims.
- Partial weight coupling reduces trainable parameters without hurting LISTA performance.
- The proposed weight structure enables unfolded ISTA to attain a linear convergence rate.
- Support selection improves the convergence rate both theoretically and empirically.
- Extensive simulations and a real-data experiment support the theoretical results.
Theoretical Linear Convergence of Unfolded ISTA and Its Practical Weights and Thresholds (Supplementary Material)
The supplementary material defines support-restricted vector and matrix notation used in the convergence analysis. These definitions select coordinates indexed by a set S and specify their ordering.
- For a vector x, x_S denotes the coordinates supported on index set S.The selected indices are ordered as i_1 ≤ i_2 ≤ ··· ≤ i_|S|.
- The size of the support index set is denoted |S|.The notation uses i_1, ···, i_|S| as the ordered elements of S.
- For a matrix W, the supplementary notation extracts rows or columns indexed by S.The displayed forms list entries using ordered indices from S.
A Proof of Theorem 1
The proof analyzes LISTA iterates near the true sparse signal under zero noise and uses threshold behavior to derive uniform convergence properties. It concludes that the relevant weight relation approaches the identity condition on supports.
- Uniform convergence makes sufficiently late iterates x_k and x_{k+1} arbitrarily close to x*.The proof introduces bounded perturbations around x* for sufficiently large iteration indices.
- The proof assumes zero noise, so the observation satisfies b = Ax*.
- 0 ≤ θ_k ≤ 3(1 + B_W)ε for sufficiently large k, so θ_k → 0.This conclusion follows for all support sizes |S| ≥ 1 under the stated conditions.
- The proof derives an error bound of 4(1 + B_W)ε for sufficiently large k.
- The resulting relation implies I − W_2^k(S,S) − W_1^k(S,:)A(S,S) approaches zero uniformly over supports with 2 ≤ |S| ≤ s.
B Proof of Theorem 2
The proof constructs suitable LISTA weights through generalized mutual coherence and an associated optimization problem. It then uses these weights to establish the parameter choice required by Theorem 2.
- Lemma 1 states that a matrix attaining the infimum in the generalized mutual-coherence definition exists.
- The optimization problem defining generalized mutual coherence is feasible because normalized columns provide at least one feasible matrix.
- Because the optimization is feasible and bounded, linear-programming theory gives an optimal solution.
- A good weight matrix satisfies unit alignment with each column of A and controls off-diagonal correlations by generalized mutual coherence.
- The proposed parameter choice is uniform over (x*, ε) ∈ X(B, s, σ) and is used to establish Theorem 2’s conclusion.
Proof of Theorem 2
The proof establishes no false positives under the threshold rule, then bounds the on-support error and extends the result uniformly over the data set. Under a sparsity condition, the resulting error bound has a positive linear-convergence exponent.
- Step 1: no false positives: The threshold rule ensures no false positives for every layer under the proof conditions.
- Step 2: error bound for one (x∗, ε): The proof next bounds the error on the true support using the threshold, weight, and noise terms.
- Practical caveat: In practice, learned thresholds that do not satisfy the proof rule may fail to guarantee no false positives across all layers.
- Step 3: error bound for the whole data set: Taking a supremum over the admissible data set converts the single-instance bound into a uniform error bound.
- Step 3: error bound for the whole data set: s < (1 + 1/˜µ)/2 makes c = −log(2˜µs −˜µ) > 0, so the uniform error bound holds.
C Proof of Theorem 3
The proof of Theorem 3 analyzes support selection under its assumptions, retains the no-false-positive property, and derives bounds involving the selected support size. It also gives iteration conditions for nonempty and sufficiently large supports.
- Step 1: proving (17): Under Assumption 1, LISTA-CPSS retains the no-false-positive property with the same parameters used for the earlier threshold rule.
- Support selection: The selected support S_k depends on the current signal and noise because the next iterate depends on both.
- Error bound: The proof relates the error bound to the number of selected nonzero elements and takes a supremum over the admissible data set.
- Step 2: proving (18): k > 1/c(log(sB/Cσ)) guarantees that the next iterate has at least one nonzero element under Assumption 2.
- Step 2: proving (18): For sufficiently large k, the selected-support quantity satisfies ˜C s_s < C.
E Training Strategy
The training strategy trains the unfolded network layer by layer, progressively reducing the learning rates of earlier layers to stabilize deeper training. This stabilization is especially useful when the unfolding depth exceeds 10 layers.
- Learning-rate schedule: Each layer introduces its parameters at learning rate α0, then trains them with decayed rates α1 and α2.
- Learning-rate schedule: The experiments use α1 = 0.2α0 and α2 = 0.02α0, while γ is set to 0.3 for multiplier decay.
- Stage-wise training: The network is trained layer by layer, with each layer trained in three stages.
- Training stabilization: Decaying earlier-layer learning rates keeps pre-trained layers near their initial positions as training proceeds to deeper layers.
- Training stabilization: The strategy works especially well for K > 10, and all reported experiments use it.
- Evaluation caveat: Curves may fluctuate because evaluation occurs after a complete training pass rather than tracking the best performance during deeper training.