Source-linked AI summary
The generalized Lasso with non-linear observations
Yaniv Plan, Roman Vershynin
TL;DR
The paper addresses whether generalized Lasso can accurately estimate structured signals from unknown non-linear observations. It models the non-linearity through effective scaling and noise, analyzes K-Lasso for general signal sets and Gaussian measurements with unknown covariance, and derives accuracy guarantees including for 1-bit compressed sensing. The results show that non-linear observations behave roughly like noisy linear observations, with error controlled by local mean width.
Problem
The paper asks whether generalized Lasso can recover structured signals from non-linear observations when practitioners use it without theoretical backing.
Method
The paper analyzes K-Lasso under a semiparametric single-index model with general signal set K and Gaussian measurement rows having unknown covariance.
Results
Non-linear observations behave roughly like scaled noisy linear observations, while K-Lasso error is controlled by local mean width and extends to unknown-covariance settings.
Takeaways & Limitations
The theory supports using K-Lasso for non-linear observations and includes a theoretical accuracy guarantee for 1-bit compressed sensing with unknown covariance.
Takeaways & Limitations
The results rely on idealized assumptions, and the authors identify softening these assumptions as future work.
Abstract
from arXiv · showhide
We study the problem of signal estimation from non-linear observations when the signal belongs to a low-dimensional set buried in a high-dimensional space. A rough heuristic often used in practice postulates that non-linear observations may be treated as noisy linear observations, and thus the signal may be estimated using the generalized Lasso. This is appealing because of the abundance of efficient, specialized solvers for this program. Just as noise may be diminished by projecting onto the lower dimensional space, the error from modeling non-linear observations with linear observations will be greatly reduced when using the signal structure in the reconstruction. We allow general signal structure, only assuming that the signal belongs to some set K in R^n. We consider the single-index model of non-linearity. Our theory allows the non-linearity to be discontinuous, not one-to-one and even unknown. We assume a random Gaussian model for the measurement matrix, but allow the rows to have an unknown covariance matrix. As special cases of our results, we recover near-optimal theory for noisy linear observations, and also give the first theoretical accuracy guarantee for 1-bit compressed sensing with unknown covariance matrix of the measurement vectors.
1. Introduction
The paper asks whether generalized Lasso can recover structured signals from unknown non-linear observations, extending its use beyond linear regression. It characterizes non-linearity as effective scaling and noise, and develops accuracy guarantees for general signal sets, unknown covariance, and 1-bit sensing.
- Motivation: Generalized Lasso is studied for reconstructing signals in a known structured set K from non-linear observations, despite being designed for linear regression.Practitioners already use Lasso for non-linear, especially binary, observations without theoretical backing.
- Model: The single-index model allows non-linearities that may be discontinuous, non-one-to-one, or unknown, while measurement rows are Gaussian with unknown covariance.The model uses independent Gaussian measurement vectors with covariance matrix Σ.
- Extensions: The results include non-linear estimation with unknown covariance and provide a theoretical accuracy guarantee for 1-bit compressed sensing without requiring covariance knowledge in the recovery algorithm.For well-conditioned covariance, its error effect can be bounded using the condition number; for subspaces, d(K,Σ) = d(K).
- Guarantees: The theory recovers the linear-model accuracy up to a small extra summand and extends subspace results to general convex sets.When K is a d-dimensional subspace, the effective dimension d(K) is comparable to d.
- Main result: The reconstruction error is controlled by the local mean width of K, which measures effective dimension at a chosen scale for general, possibly non-conic structures.For tangent-cone structure, the relevant effective dimension is based on the tangent cone at µx.
- Main result: Non-linear observations behave for K-Lasso like noisy linear observations y_i = µx + σz_i, with scaling µ and noise σ determined by the non-linearity.The induced noise may have heavy tails, requiring analysis beyond standard independent or sub-Gaussian noise techniques.
2. Related literature
Prior theory covers linear reconstruction and nonlinearity, but this work focuses on how general low-dimensional signal structure improves reconstruction from nonlinear observations.
- Linear observations: Gaussian mean width provides an alternative dimension measure that controls restricted-matrix conditioning through the tangent cone.Compressed sensing theory uses squared Gaussian mean width to characterize sufficient observation counts.
- Linear observations: Theorem 1.4 extends linear-observation theory to nonlinear observations and general signal sets, recovering the linear result up to an absolute constant.For a d-dimensional subspace, the effective dimension d(K) is comparable to d.
- Nonlinearity and low-dimensional structure: Earlier literature on semiparametric single-index models is predominantly asymptotic and does not address gains from general low-dimensional structure.The paper positions its contribution as a precise characterization of those gains.
- Nonlinearity and low-dimensional structure: For sparse signals, the effective dimension is O(s log(n/s)), so O(s log(n/s)) measurements suffice for estimation.In the nonlinear case, induced modeling noise is reduced proportionally to s log(n/s)/m.
- Nonlinearity and low-dimensional structure: One-bit compressed sensing studies binary quantization, a nonlinear setting motivated by signal-processing and statistical applications.Its discrete observations introduce challenges absent from unquantized models.
- Nonlinearity and low-dimensional structure: Related work studies general low-dimensional sets with general nonlinearities, while this paper claims tighter results and further extensions.The comparison includes frameworks that can be specialized to K-Lasso but impose stronger assumptions or do not exploit local structure.
3. Specialization to 1-bit compressed sensing
For 1-bit compressed sensing, the K-Lasso reconstructs sparse signals from sign measurements with near-optimal observation scaling, including reasonably conditioned unknown covariance.
- 1-bit compressed sensing: m = O(s log(n/s)) observations suffice for K-Lasso accuracy under 1-bit quantization.Here K is a scaled ℓ1 ball and x is s-sparse.
- 1-bit compressed sensing: The same accuracy bound remains valid for general covariance structures when Σ is reasonably well conditioned.This follows by combining Corollary 1.6 with the 1-bit result.
- 1-bit compressed sensing: Even highly non-linear 1-bit observations can be handled accurately when observations significantly exceed the signal’s effective dimension.The effective dimension is represented through the tangent-cone mean width.
4. Proof of main results
The proofs recast non-linear observations as a scaled linear model with dependent, potentially non-centered noise, then control expected loss and deviations using Gaussian geometry and local complexity.
- Scaled linear reduction: The induced residual z acts as noise despite dependence on A and x and the possibility of nonzero mean.This dependence prevents direct use of standard independent-noise arguments.
- Scaled linear reduction: The single-index model yields the decomposition y = µx + z, with µ defined from the non-linearity and z treated as the residual.The model assumption yi = f(⟨ai, x⟩) gives the relevant expectation identity.
- Expected loss: Replacing the original loss by an equivalent rescaled loss makes its expectation well behaved while preserving the K-Lasso minimizer.The replacement only squares, subtracts a constant, and rescales the loss.
- Expected loss: µx minimizes the expected loss, so the proof reduces to controlling deviations of the loss terms from expectation.This establishes the population target before the high-probability analysis.
- Tangent-cone analysis: Gordon’s escape-through-the-mesh theorem controls conditioning on the tangent cone, while Gaussian-width bounds control the residual term.The argument combines two high-probability events whose intersection has probability at least 0.99.
- Residual control: A projection argument mostly decouples z from A, using Gaussian independence between P⊥A^T and PA^T.Conditioning on z then identifies the projected Gaussian term through the local mean width.
- General-set analysis: For general convex sets, star-shapedness and uniform ℓ1 deviation bounds extend the argument beyond tangent cones at scales at least t.The proof applies the result to K − µx and uses monotonicity to handle errors larger than t.
5. discussion
The paper concludes that K-Lasso accuracy under single-index non-linearity is governed by local mean width, while highlighting Gaussian-design and model-specification boundaries.
- Discussion: Under the single-index model, K-Lasso behaves roughly like K-Lasso for noisy linear observations y_i = µx + σz_i.The parameters µ = µ(f) and σ = σ(f) have simple expressions, and error is controlled by local mean width.
- Discussion: The theory relies on idealized assumptions that the authors identify as targets for future theoretical and practical work.The discussion specifically emphasizes softening these assumptions.
- Limitations and extensions: The clean result assumes a Gaussian design; universality for non-Gaussian or general design matrices remains unresolved, especially for extremely sparse x.The authors conjecture an extra sparsity-dependent error term for independent subGaussian entries.
- Limitations and extensions: Robustness remains open when the single-index model is only approximate or when µx does not exactly lie in K.These are identified as directions for handling model inaccuracies.
- Design implications: If the non-linearity is designable, explicit µ(f) and σ(f) can potentially be tuned to optimize reconstruction error.Quantization is given as the motivating example.