Learning a Compressed Sensing Measurement Matrix via Gradient Unrolling

Abstract

Linear encoding of sparse vectors is widely popular, but is commonly data-independent -- missing any possible extra (but a priori unknown) structure beyond sparsity. In this paper we present a new method to learn linear encoders that adapt to data, while still performing well with the widely used ${\ell }_1$ decoder. The convex ${\ell }_1$ decoder prevents gradient propagation as needed in standard gradient-based training. Our method is based on the insight that unrolling the convex decoder into $T$ projected subgradient steps can address this issue. Our method can be seen as a data-driven way to learn a compressed sensing measurement matrix. We compare the empirical performance of 10 algorithms over 6 sparse datasets (3 synthetic and 3 real). Our experiments show that there is indeed additional structure beyond sparsity in the real datasets; our method is able to discover it and exploit it to create excellent reconstructions with fewer measurements (by a factor of 1.1-3x) compared to the previous state-of-the-art methods. We illustrate an application of our method in learning label embeddings for extreme multi-label classification, and empirically show that our method is able to match or outperform the precision scores of SLEEC, which is one of the state-of-the-art embedding-based approaches.

17 pages, 7 tables, 8 figures, published in ICML 2019; part of this work was done while Shanshan was an intern at Google Research, New York

Cited by in corpus (11)

• Learning to Optimize: A Primer and A Benchmark
• Joint Design of Measurement Matrix and Sparse Support Recovery Method via Deep Auto-encoder
• Compressed CSI Feedback With Learned Measurement Matrix for mmWave Massive MIMO
• Theoretical Interpretation of Learned Step Size in Deep-Unfolded Gradient Descent
• Learning Illumination Patterns for Coded Diffraction Phase Retrieval
• Jointly Sparse Signal Recovery and Support Recovery via Deep Learning with Applications in MIMO-based Grant-Free Random Access
• InSPECtor: an end-to-end design framework for compressive pixelated hyperspectral instruments
• Non-linear, Sparse Dimensionality Reduction via Path Lasso Penalized Autoencoders
• Jointly Sparse Support Recovery via Deep Auto-encoder with Applications in MIMO-based Grant-Free Random Access for mMTC
• Jointly Sparse Signal Recovery via Deep Auto-Encoder and Parallel Coordinate Descent Unrolling
• Compressed Sensing via Measurement-Conditional Generative Models