Journal article
A simple homotopy proximal mapping algorithm for compressive sensing
Machine learning, Vol.108(6), pp.1019-1056
06/01/2019
DOI: 10.1007/s10994-018-5772-7
Abstract
In this paper, we present novel yet simple homotopy proximal mapping algorithms for reconstructing a sparse signal from (noisy) linear measurements of the signal or for learning a sparse linear model from observed data, where the former task is well-known in the field of compressive sensing and the latter task is known as model selection in statistics and machine learning. The algorithms adopt a simple proximal mapping of the 1 norm at each iteration and gradually reduces the regularization parameter for the 1 norm. We prove a global linear convergence of the proposed homotopy proximal mapping (HPM) algorithms for recovering the sparse signal under three different settings (i) sparse signal recovery under noiseless measurements, (ii) sparse signal recovery under noisy measurements, and (iii) nearly-sparse signal recovery under sub-Gaussian noisy measurements. In particular, we show that when the measurement matrix satisfies restricted isometric properties (RIP), one of the proposed algorithms with an appropriate setting of a parameter based on the RIP constants converges linearly to the optimal solution up to the noise level. In addition, in setting (iii), a practical variant of the proposed algorithms does not rely on the RIP constants and our results for sparse signal recovery are better than the previous results in the sense that our recovery error bound is smaller. Furthermore, our analysis explicitly exhibits that more observations lead to not only more accurate recovery but also faster convergence. Finally our empirical studies provide further support for the proposed homotopy proximal mapping algorithm and verify the theoretical results.
Details
- Title: Subtitle
- A simple homotopy proximal mapping algorithm for compressive sensing
- Creators
- Tianbao Yang - University of IowaLijun Zhang - Nanjing UniversityRong Jin - Alibaba GroupShenghuo Zhu - Alibaba GroupZhi-Hua Zhou - Nanjing University
- Resource Type
- Journal article
- Publication Details
- Machine learning, Vol.108(6), pp.1019-1056
- Publisher
- Springer Nature
- DOI
- 10.1007/s10994-018-5772-7
- ISSN
- 0885-6125
- eISSN
- 1573-0565
- Number of pages
- 38
- Grant note
- 1545995 / NSF; National Science Foundation (NSF) 61751306 / NSFC; National Natural Science Foundation of China (NSFC) 2018YFB1004300 / National Key RAMP;D Program of China BK20160658 / JiangsuSF 2017QNRC001 / YESS
- Language
- English
- Date published
- 06/01/2019
- Academic Unit
- Computer Science
- Record Identifier
- 9984259416402771
Metrics
1 Record Views