Theoretical Linear Convergence of Unfolded ISTA and its Practical Weights and Thresholds

Abstract

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.

18 pages, 6 figures, 1 table. Accepted as spotlight oral in NIPS 2018

Cited by in corpus (46)

• Model-Driven Deep Learning for MIMO Detection
• Plug-and-Play Methods for Integrating Physical and Learned Models in Computational Imaging
• A Review on Deep Learning in Medical Image Reconstruction
• Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problem
• Learning to Optimize: A Primer and A Benchmark
• Deep Learning Methods for Solving Linear Inverse Problems: Research Directions and Paradigms
• $\mathbf{\gamma }$-Net: Superresolving SAR Tomographic Inversion via Deep Learning
• Binary MIMO Detection via Homotopy Optimization and Its Deep Adaptation
• Recent Advances in Imaging Around Corners
• RNA Secondary Structure Prediction By Learning Unrolled Algorithms
• CDLNet: Noise-Adaptive Convolutional Dictionary Learning Network for Blind Denoising and Demosaicing
• ADMM-Net for Communication Interference Removal in Stepped-Frequency Radar
• ATASI-Net: An Efficient Sparse Reconstruction Network for Tomographic SAR Imaging with Adaptive Threshold
• Deep Coupled-Representation Learning for Sparse Linear Inverse Problems with Side Information
• Basis Pursuit Denoising via Recurrent Neural Network Applied to Super-resolving SAR Tomography
• Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection
• Learning to Optimize in Swarms
• Frank-Wolfe Network: An Interpretable Deep Structure for Non-Sparse Coding
• Theoretical Interpretation of Learned Step Size in Deep-Unfolded Gradient Descent
• Robust Time-Frequency Reconstruction by Learning Structured Sparsity
• Learnable Descent Algorithm for Nonsmooth Nonconvex Image Reconstruction
• Learning step sizes for unfolded sparse coding
• Model-inspired Deep Learning for Light-Field Microscopy with Application to Neuron Localization
• Feasibility-based Fixed Point Networks
• GLAD: Learning Sparse Graph Recovery
• A Design Space Study for LISTA and Beyond
• Scalable Deep Compressive Sensing
• MetaInv-Net: Meta Inversion Network for Sparse View CT Image Reconstruction
• Algorithm Unrolling for Massive Access via Deep Neural Network with Theoretical Guarantee
• Methods for Recovering Conditional Independence Graphs: A Survey
• On the convergence of group-sparse autoencoders
• Phase Retrieval using Expectation Consistent Signal Recovery Algorithm based on Hypernetwork
• Understanding Deep Architectures with Reasoning Layer
• A Novel Learnable Gradient Descent Type Algorithm for Non-convex Non-smooth Inverse Problems
• Fully Trainable and Interpretable Non-Local Sparse Models for Image Restoration
• Learning Simple Thresholded Features with Sparse Support Recovery
• Deeply-Sparse Signal rePresentations ($\text{D}{\text{S}}^2\text{P}$)
• Learning Cluster Structured Sparsity by Reweighting
• Learned Interpretable Residual Extragradient ISTA for Sparse Coding
• Deep-Learned Approximate Message Passing for Asynchronous Massive Connectivity
• Neurally Augmented ALISTA
• QISTA-Net: DNN Architecture to Solve ${\ell }_q$-norm Minimization Problem and Image Compressed Sensing
• Theoretical Linear Convergence of Deep Unfolding Network for Block-Sparse Signal Recovery
• Compressed Sensing via Measurement-Conditional Generative Models
• Algorithm Unfolding for Block-sparse and MMV Problems with Reduced Training Overhead
• Deep Learning Meets SAR