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.
Introduction
In high-dimensional statistics, the goal is often to recover a structured signal—such as a sparse vector or a low-rank matrix—from a limited number of observations ($n \ll d$). While the linear model $Y = X\Theta + \epsilon$ has been extensively studied, real-world data frequently exhibits nonlinear relationships. Recovering signals from such nonlinear measurements presents two major hurdles: transformation bias, where simple inversions of the nonlinearity distort noise distributions, and non-convexity, which complicates optimization.
This paper demonstrates that the Iterative Hard Thresholding (IHT) algorithm, traditionally used for linear recovery, is remarkably effective for nonlinear estimation. We prove that IHT converges linearly to an estimator with optimal statistical accuracy, even when starting from an arbitrary initialization.
The Nonlinear Structured Signal Model
We consider the model: $$Y = f(\langle X, \Theta^* \rangle) + \epsilon$$ where $f$ is a known nonlinear link function and $\Theta^*$ is the structured signal of interest. Standard approaches often attempt to "linearize" the problem by applying $f^{-1}$ to the observations $Y$. However, if $Y$ is noisy, $f^{-1}(Y)$ introduces significant bias because the noise $\epsilon$ is no longer zero-mean after the transformation. By contrast, our approach optimizes the nonlinear least-squares loss directly, maintaining robustness to stochastic noise.
Iterative Hard Thresholding (IHT)
The proposed method utilizes a projected gradient descent framework:
- Gradient Step: Update the estimate by moving in the direction that minimizes the nonlinear least-squares loss.
- Truncation Step: Project the updated estimate back onto the set of structured signals. For sparse vectors, this involves keeping the $s$ largest entries; for low-rank matrices, it involves keeping the top $s$ singular values via Singular Value Decomposition (SVD).
The key theoretical finding is that under a Restricted Isometry Property (RIP)—the same condition used in linear compressed sensing—the algorithm converges geometrically to the true signal, provided $f$ is monotone and has bounded derivatives.
Numerical Evidence
The theoretical results are supported by extensive simulations on synthetic data and a real-world image reconstruction task.
Sparse Vector Recovery
In simulations with sparse vectors, the estimation error was found to scale as $O(\sqrt{s^* \log d / n})$, matching the minimax optimal rate. As shown in Figure 1, the nonlinear IHT significantly outperforms the Lasso baseline, which fails to maintain accuracy as the noise level or nonlinearity increases.
Low-Rank Matrix Recovery
The algorithm's versatility extends to low-rank matrix estimation. Similar to the sparse case, the error follows the predicted theoretical scaling. Figure 2 illustrates that the nonlinear IHT maintains low error rates where standard methods like Non-negative Least Squares (NNLS) applied to transformed data begin to diverge.
Image Reconstruction
To demonstrate practical utility, the authors reconstructed a high-resolution image of Nassau Hall at Princeton University. By treating the image as a structured signal (via its singular value decomposition) and using a nonlinear link function $f(u) = 2u + \cos u$, the algorithm achieved a relative reconstruction error of only 6%, showcasing its potential for complex image processing tasks.
Conclusion
This work establishes that IHT is a powerful tool for nonlinear high-dimensional estimation. By proving linear convergence from arbitrary initialization and achieving minimax optimal rates under standard RIP conditions, the authors provide a robust framework for structured signal recovery. Future work may extend these results to non-monotone functions, such as those found in phase retrieval or one-bit compressed sensing.
Summary updated