Learning a Compressed Sensing Measurement Matrix via Gradient Unrolling

Shanshan Wu, Alex Dimakis, Sujay Sanghavi, Felix Yu, Daniel Holtmann-Rice, Dmitry Storcheus, Afshin Rostamizadeh, Sanjiv Kumar
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:6828-6839, 2019.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-wu19b, title = {Learning a Compressed Sensing Measurement Matrix via Gradient Unrolling}, author = {Wu, Shanshan and Dimakis, Alex and Sanghavi, Sujay and Yu, Felix and Holtmann-Rice, Daniel and Storcheus, Dmitry and Rostamizadeh, Afshin and Kumar, Sanjiv}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {6828--6839}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/wu19b/wu19b.pdf}, url = {https://proceedings.mlr.press/v97/wu19b.html}, 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.} }
Endnote
%0 Conference Paper %T Learning a Compressed Sensing Measurement Matrix via Gradient Unrolling %A Shanshan Wu %A Alex Dimakis %A Sujay Sanghavi %A Felix Yu %A Daniel Holtmann-Rice %A Dmitry Storcheus %A Afshin Rostamizadeh %A Sanjiv Kumar %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-wu19b %I PMLR %P 6828--6839 %U https://proceedings.mlr.press/v97/wu19b.html %V 97 %X 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.
APA
Wu, S., Dimakis, A., Sanghavi, S., Yu, F., Holtmann-Rice, D., Storcheus, D., Rostamizadeh, A. & Kumar, S.. (2019). Learning a Compressed Sensing Measurement Matrix via Gradient Unrolling. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:6828-6839 Available from https://proceedings.mlr.press/v97/wu19b.html.

Related Material