Source-linked AI summary
Compressed Sensing with Nonlinear Observations and Related Nonlinear Optimisation Problems
Thomas Blumensath
TL;DR
The paper asks whether Compressed Sensing recovery remains possible when measurements are nonlinear rather than linear. It applies Iterative Hard Thresholding under Jacobian-based and related structural conditions, showing recovery for non-convex constraint sets and near-optimality in nonlinear optimisation.
Problem
Compressed Sensing theory has largely assumed linear measurements, motivating the study of recovery from nonlinear observations.
Method
The paper applies Iterative Hard Thresholding to nonlinear measurements and to nonlinear optimisation over sparsity and union-of-subspaces constraints.
Results
Under a Restricted Isometry Property for the Jacobian and sufficiently small linearisation error, Iterative Hard Thresholding can recover signals from non-convex constraint sets with similar error bounds to linear Compressed Sensing.
Takeaways & Limitations
Restricted Isometry conditions on the Jacobian provide tools for nonlinear Compressed Sensing, while Restricted Strict Convexity is sufficient for near-optimal points in related nonlinear optimisation problems.
Takeaways & Limitations
In Hilbert spaces, the Restricted Isometry Property cannot hold for nonaffine Φ and all y, so general recovery requires Jacobian-based conditions and good linear approximations.
Abstract
from arXiv · showhide
Non-convex constraints have recently proven a valuable tool in many optimisation problems. In particular sparsity constraints have had a significant impact on sampling theory, where they are used in Compressed Sensing and allow structured signals to be sampled far below the rate traditionally prescribed. Nearly all of the theory developed for Compressed Sensing signal recovery assumes that samples are taken using linear measurements. In this paper we instead address the Compressed Sensing recovery problem in a setting where the observations are non-linear. We show that, under conditions similar to those required in the linear setting, the Iterative Hard Thresholding algorithm can be used to accurately recover sparse or structured signals from few non-linear observations. Similar ideas can also be developed in a more general non-linear optimisation framework. In the second part of this paper we therefore present related result that show how this can be done under sparsity and union of subspaces constraints, whenever a generalisation of the Restricted Isometry Property traditionally imposed on the Compressed Sensing system holds.
1 Introduction
Compressed Sensing uses non-convex constraints such as sparsity to recover signals from undersampled measurements, but this paper extends the setting from linear observations to nonlinear optimisation problems.
- Classical Compressed Sensing: Compressed Sensing recovers sparse signals from M linear measurements represented by y = Φx + e, even when M << N under suitable conditions.Sparsity supplies additional structure when the linear system is not uniquely invertible.
- Classical Compressed Sensing: Sparsity can permit recovery with roughly O(M/log(N)) non-zero elements using polynomial-time algorithms under stricter conditions on Φ.Without additional structure, recovery is generally combinatorial and NP-hard.
- Generalised Constraints: The framework extends beyond sparse vectors to non-convex sets, including unions of subspaces, low-rank matrices, and structured sparse models.The union-of-subspaces model allows the signal to lie in one of several unknown linear subspaces.
- Nonlinear Optimisation: Under a general non-convex constraint set A, recovery can be formulated as minimising the sum of squared observation error over vectors in A.The paper then replaces the linear observation objective with a more general nonlinear function f(x).
- Nonlinear Optimisation: The paper studies nonlinear Compressed Sensing with f(x) = ∥y−Φ(x)∥ and also considers the broader nonlinear optimisation problem independently.Its nonlinear measurement mapping Φ(x) maps between vector spaces.
2 Non-Linear Compressed Sensing
The paper extends Compressed Sensing recovery to nonlinear measurements by combining local linearisation with Iterative Hard Thresholding over non-convex constraint sets. Recovery is supported when the linearised systems satisfy a Restricted Isometry Property and nonlinearisation errors remain controlled.
- Problem setting: Nonlinear Compressed Sensing models measurements through a nonlinear mapping between Hilbert spaces, with bounded observation error and signals constrained to a known non-convex set.The framework includes constraint sets described as unions of subspaces.
- Algorithm: The generalized IHT method replaces hard thresholding with a projection-like map onto the constraint set A.The projection may be approximate or non-unique; the analysis assumes A is proximal so the required optima lie in A.
- Algorithm: At each iteration, the nonlinear measurement map is approximated by an affine Taylor expansion whose linear operator is evaluated at the current reference point.The resulting operator generally depends on the reference point x⋆, so the IHT update uses a local linearisation rather than a fixed measurement matrix.
- Recovery guarantee: Recovery holds under conditions similar to linear IHT when the linearised operators satisfy RIP and the linearisation error is sufficiently small.The theorem imposes bounds involving α, β, µ, and the nonlinear error term; convergence requires the associated contraction factor to remain below one.
- Example: For elementwise sensor nonlinearities f(x) = x + h(x), bounds on h′ and the base operator’s RIP yield conditions for applying the nonlinear recovery theory.The example analyzes the Jacobian, its RIP constants, and the deviation between the nonlinear map and its linearisation.
3 The Iterative Hard Thresholding Algorithm for NonLinear Optimisation
The paper extends Iterative Hard Thresholding to nonlinear optimization over unions of subspaces, using gradient-based updates and generalized projections. Under Restricted Strict Convexity, the method finds a point close to the constrained minimizer, while applicability to nonlinear Compressed Sensing is limited in general Hilbert spaces.
- Problem: The optimization problem minimizes a nonlinear function f(x) subject to x belonging to a union of subspaces A.The framework generalizes sparse-signal recovery to non-convex constraint sets.
- Algorithm: The update direction is the gradient of f(x), interpreted through Fréchet derivatives and Riesz representation in general Hilbert spaces.In Euclidean spaces, this gradient is the ordinary gradient; the update is followed by a generalized projection onto A.
- Algorithm: The generalized IHT, also called a Projected Landweber Algorithm, replaces hard thresholding with a map P_A and uses a step size μ.The initialization is x_0 = 0, with μ chosen according to the theorem’s conditions.
- Theoretical guarantee: Restricted Strict Convexity is sufficient for IHT to find a vector close to the true minimizer over A.The theorem assumes A is a union of subspaces and imposes conditions on f and the relevant subspace differences.
- Proof: The proof controls the distance between successive iterates and the optimum using projections onto a subspace containing x_opt, x_n, and x_n+1.The argument combines a lemma, the Restricted Strict Convexity Property, and a contraction factor that decreases with iteration.
- Applicability: For nonlinear Compressed Sensing in Hilbert spaces, Restricted Strict Convexity cannot hold for all observations unless the measurement map is affine on relevant subspaces.The paper instead identifies the Jacobian’s Restricted Isometry Property and good linear approximations as more suitable recovery tools.
4 Conclusions
The conclusions generalize Compressed Sensing to nonlinear measurements and non-convex constraints. They report recovery guarantees for IHT under a Jacobian RIP and near-optimal solutions under Restricted Strict Convexity.
- Nonlinear Compressed Sensing: A Jacobian satisfying a Restricted Isometry Property allows IHT to recover signals from non-convex constraint sets with error bounds similar to Compressed Sensing.This extends the framework beyond sparse signals and linear measurements.
- Nonlinear optimization: Restricted Strict Convexity is sufficient for IHT to find points near the optimal solution in nonlinear optimization under non-convex constraints.The result applies to the related, more general setting studied in the paper’s second part.