Abstract: In this paper, we study the issue of estimating a structured signal $x_0 \in \mathbb{R}^n$ from non-linear and noisy Gaussian observations. Supposing that $x_0$ is contained in a certain convex subset $K \subset \mathbb{R}^n$, we prove that accurate recovery is already feasible if the number of observations exceeds the effective dimension of $K$, which is a common measure for the complexity of signal classes. It will turn out that the possibly unknown non-linearity of our model affects the error rate only by a multiplicative constant. This achievement is based on recent works by Plan and Vershynin, who have suggested to treat the non-linearity rather as noise which perturbs a linear measurement process. Using the concept of restricted strong convexity, we show that their results for the generalized Lasso can be extended to a fairly large class of convex loss functions. Moreover, we shall allow for the presence of adversarial noise so that even deterministic model inaccuracies can be coped with. These generalizations particularly give further evidence of why many standard estimators perform surprisingly well in practice, although they do not rely on any knowledge of the underlying output rule. To this end, our results provide a unified and general framework for signal reconstruction in high dimensions, covering various challenges from the fields of compressed sensing, signal processing, and statistical learning.
Introduction
In high-dimensional estimation, the goal is often to recover a signal $x_0 \in \mathbb{R}^n$ from $m$ observations, where $m \ll n$. Traditional Compressed Sensing relies on a linear model: $y = Ax_0 + \text{noise}$. However, real-world sensors are rarely perfectly linear; they may be binary, saturated, or subject to unknown non-linear distortions. This research addresses whether standard convex optimization tools can accurately recover structured signals even when the observations are non-linear and the exact measurement process is unknown.
The Semiparametric Single-Index Model
The study analyzes a semiparametric single-index model, where observations follow $y_i = f(\langle a_i, x_0 \rangle)$. Here, $a_i$ are Gaussian measurement vectors, and $f$ is a potentially unknown non-linearity. The proposed approach uses a generalized estimator:
$$\min_{x \in K} \frac{1}{m} \sum_{i=1}^m \mathcal{L}(\langle a_i, x \rangle, \tilde{y}_i)$$
where $K$ is a convex set representing the signal's structure (e.g., an $\ell_1$-ball for sparsity) and $\mathcal{L}$ is a general convex loss function.
Restricted Strong Convexity and Loss Curvature
A central pillar of this framework is Restricted Strong Convexity (RSC). This property ensures that the loss function has sufficient "curvature" around the true signal to allow for stable estimation. If the loss function is too flat, small perturbations in the loss (due to noise or non-linearity) can lead to large errors in the estimated signal $\hat{x}$.
As illustrated above, a sharper minimum (a) provides a more stable estimate $\hat{x}$ relative to the scaled true signal $\mu x_0$ than a flatter loss function (b). The paper utilizes Mendelson’s Small Ball Method to establish RSC for a broad class of loss functions without relying on overly simplistic concentration inequalities.
Geometric Complexity of Signal Sets
The number of measurements $m$ required for successful recovery is determined by the "effective dimension" or Gaussian mean width of the signal class $K$. This geometric measure quantifies the complexity of the set $K$ in the direction of the measurement vectors.
By employing Local Mean Width, the author improves the error decay rate from $O(m^{-1/4})$ found in earlier global analyses to the more optimal $O(m^{-1/2})$. This allows for tighter error bounds that scale gracefully with the number of observations.
Key Insights and Results
- Non-linearity as "Noise": Non-linear observations can be mathematically treated as linear observations perturbed by noise. This allows researchers to apply linear intuition to non-linear problems.
- Blind Recovery: The estimator does not need to know the function $f$. Standard solvers like Lasso or Logistic Regression can be used even if the sensor distortion is unknown.
- Recovery Guarantee: If $m$ exceeds the effective dimension of $K$, the estimator $\hat{x}$ satisfies: $$\|\hat{x} - \mu x_0\|_2 \lesssim \frac{\text{complexity}}{\sqrt{m}} + \text{adversarial noise}$$ where $\mu$ is a scaling factor related to the correlation between the non-linearity and a linear model.
Conclusion and Future Directions
This work provides a unified framework for signal reconstruction, showing that the choice of loss function $\mathcal{L}$ primarily affects constant factors rather than the fundamental recovery rate. While the current theory is robust for Gaussian data, future work may explore extensions to non-convex structures (like neural network priors) and multi-index models where the output depends on multiple projections of the signal.
Summary updated