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.


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.

Related Material