Nonlinear Structured Signal Estimation in High Dimensions via Iterative Hard Thresholding

Kaiqing Zhang, Zhuoran Yang, Zhaoran Wang
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:258-268, 2018.

Abstract

We study the high-dimensional signal estimation problem with nonlinear measurements, where the signal of interest is either sparse or low-rank. In both settings, our estimator is formulated as the minimizer of the nonlinear least-squares loss function under a combinatorial constraint, which is obtained efficiently by the iterative hard thresholding (IHT) algorithm. Although the loss function is non-convex due to the nonlinearity of the statistical model, the IHT algorithm is shown to converge linearly to a point with optimal statistical accuracy using arbitrary initialization. Moreover, our analysis only hinges on conditions similar to those required in the linear case. Detailed numerical experiments are included to corroborate the theoretical results.

Cite this Paper


BibTeX
@InProceedings{pmlr-v84-zhang18a, title = {Nonlinear Structured Signal Estimation in High Dimensions via Iterative Hard Thresholding}, author = {Zhang, Kaiqing and Yang, Zhuoran and Wang, Zhaoran}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {258--268}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/zhang18a/zhang18a.pdf}, url = {https://proceedings.mlr.press/v84/zhang18a.html}, abstract = {We study the high-dimensional signal estimation problem with nonlinear measurements, where the signal of interest is either sparse or low-rank. In both settings, our estimator is formulated as the minimizer of the nonlinear least-squares loss function under a combinatorial constraint, which is obtained efficiently by the iterative hard thresholding (IHT) algorithm. Although the loss function is non-convex due to the nonlinearity of the statistical model, the IHT algorithm is shown to converge linearly to a point with optimal statistical accuracy using arbitrary initialization. Moreover, our analysis only hinges on conditions similar to those required in the linear case. Detailed numerical experiments are included to corroborate the theoretical results.} }
Endnote
%0 Conference Paper %T Nonlinear Structured Signal Estimation in High Dimensions via Iterative Hard Thresholding %A Kaiqing Zhang %A Zhuoran Yang %A Zhaoran Wang %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-zhang18a %I PMLR %P 258--268 %U https://proceedings.mlr.press/v84/zhang18a.html %V 84 %X We study the high-dimensional signal estimation problem with nonlinear measurements, where the signal of interest is either sparse or low-rank. In both settings, our estimator is formulated as the minimizer of the nonlinear least-squares loss function under a combinatorial constraint, which is obtained efficiently by the iterative hard thresholding (IHT) algorithm. Although the loss function is non-convex due to the nonlinearity of the statistical model, the IHT algorithm is shown to converge linearly to a point with optimal statistical accuracy using arbitrary initialization. Moreover, our analysis only hinges on conditions similar to those required in the linear case. Detailed numerical experiments are included to corroborate the theoretical results.
APA
Zhang, K., Yang, Z. & Wang, Z.. (2018). Nonlinear Structured Signal Estimation in High Dimensions via Iterative Hard Thresholding. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:258-268 Available from https://proceedings.mlr.press/v84/zhang18a.html.

Related Material