PaperlayerView exact revision on arXiv

Source-linked AI summary

Instance Optimal Sparse Recovery from Nonlinear Observations: A Unified Framework

Junren Chen, Arian Maleki

arXiv:2609.02120v1cs.ITeess.SPmath.ST

TL;DR

Instance-optimal sparse recovery for approximately sparse signals remains limited for nonlinear measurements. This paper develops a signal-dependent RAIC framework for iterative hard thresholding and establishes guarantees across sparse phase retrieval, one-bit compressed sensing, and sparse ReLU regression, including O(s^3) measurements for sparse phase retrieval.

  • Problem

    The paper addresses limited instance-optimal sparse recovery guarantees for approximately sparse signals under nonlinear measurements, where exact recovery may be impossible even for sparse signals.

    Source: §1 · p. 2

  • Method

    The framework uses a signal-dependent restricted approximate invertibility condition for a gradient map to establish instance optimality of iterative hard thresholding.

    Source: §1.1 · p. 3, §2.1 · p. 7, §6 · p. 22

  • Results

    The framework obtains instance-optimal guarantees for sparse phase retrieval, one-bit compressed sensing, and sparse ReLU regression under Gaussian designs, with sparse phase retrieval using O(s^3) measurements up to logarithmic factors.

    Source: §3.2.1 · p. 15, §4.2.1 · p. 18, §6 · p. 22

  • Takeaways & Limitations

    The results provide a unified route to robust sparse recovery guarantees across several nonlinear measurement models.

    Source: §1 · p. 2, §6 · p. 22

    An additional logarithmic factor appears in the model error, and whether it can be removed remains open.

    Source: §4.2 · p. 17

Abstract

from arXiv · show

This paper develops a unified framework for instance optimal sparse recovery from nonlinear observations. The main ingredient is a signal-dependent restricted approximate invertibility condition (RAIC) of some gradient, which leads to the instance optimality of iterative hard thresholding. Under Gaussian designs, we apply the proposed framework to phaseless, one-bit, and ReLU measurements, which correspond to the problems of sparse phase retrieval, one-bit compressed sensing, and sparse ReLU regression, respectively. For sparse phase retrieval, we propose a variant of thresholded amplitude flow and show its instance optimality under $O(s^3)$ measurements (up to logarithmic factors), where $s$ is the sparsity level. To our best knowledge, this is the first instance optimal efficient algorithm for sparse phase retrieval and complements Gao, Wang and Xu (2016) that achieved this via a computationally intractable program. In one-bit compressed sensing, we establish the instance optimality of normalized binary iterative hard thresholding and strengthen the recent result of Matsumoto and Mazumdar (2024). In sparse ReLU regression, it is shown that a slight variant of the algorithm in Soltanolkotabi (2017) is instance optimal. Moreover, $(\ell_2,\ell_2)$ non-uniform instance optimal guarantees are obtained for these problems. The analysis is built upon a number of high-dimensional concentration bounds, including bounds on restricted eigenvalues and a novel instance-dependent hyperplane tessellation result.

1 Introduction

The paper asks how to obtain instance-optimal sparse recovery from nonlinear observations when signals are only approximately sparse and exact recovery may be impossible. It develops a unified IHT-based framework and applies it to sparse phase retrieval, one-bit compressed sensing, and sparse ReLU regression.

1 Introduction

  • Instance optimality controls recovery error by distance to the best s-sparse approximation, but nonlinear observations require signal spaces and error targets beyond exact sparse recovery.One-bit sensing loses signal norm, and exact recovery may be impossible even for s-sparse signals; statistically optimal error is therefore the attainable goal.Source: §1 · p. 2

1.1 Main Contributions

  • A signal-dependent RAIC for problem-specific gradients yields instance-optimal normalized or standard IHT over signals near the sparse model.The framework decomposes the signal space into near-sparse and complementary regions, extending prior RAIC control with a signal-dependent error term.Source: §1.1 · p. 3
  • The framework establishes IHT-type instance-optimal guarantees for sparse phase retrieval, one-bit compressed sensing, and ReLU regression under Gaussian designs.For sparse phase retrieval, a thresholded amplitude-flow variant uses ˜O(s^3) measurements uniformly; Theorem 4.1 gives the first signal-dependent instance-optimal result known for one-bit compressed sensing.Source: §1.1 · p. 3, §1.2 · p. 5

1.3 Additional Related Works

  • The paper develops a unified framework for instance-optimal nonlinear sparse recovery using concentration bounds, embedding guarantees, and restricted-eigenvalue bounds, with major applications presented in Sections 3–5.Its guarantees are achieved by the computationally fast procedure IHT, whose analysis is based on the RAIC.Source: §1.1 · p. 4, §1.3 · p. 6, §1.4 · p. 7

1.2 Related Works

  • Unlike prior nonlinear recovery results that are model-specific, intractable, or only exact/non-uniform, the paper provides efficient instance-optimal guarantees, including the first efficient uniformly instance-optimal sparse phase-retrieval solver under m = ˜Ω(s^3) [33] [70].It also improves treatment of model error for signals close to the sparse set and introduces a new signal-dependent hyperplane tessellation result for the one-bit analysis.Source: §1.2 · p. 4, §1.3 · pp. 5–6

2 Unified Framework

The framework uses signal-dependent RAIC to analyze IHT and NIHT, yielding linear convergence and instance-optimal recovery bounds that separate optimization, statistical, and instance-dependent errors. It provides both uniform guarantees over signal classes and sharper non-uniform guarantees for fixed signals.

2.1 RAIC and (Normalized) IHT

  • IHT updates by hard-thresholding a gradient step, while NIHT adds normalization when the target lies on the unit sphere.The framework constructs a gradient map h_x and uses x_{t+1}=H_s(x_t−η·h_x(x_t)); normalization also extends to known signal norms β.Source: §2.1 · p. 7
  • Under a sufficiently large constraint set and an error function μ_1∥u−x∥_2+μ_2, RAIC with proper initialization gives linear convergence for IHT and NIHT.The resulting optimization error decays geometrically, with convergence statements provided separately for IHT and NIHT.Source: §2.1 · pp. 7–8

2.2 From Signal-Dependent RAIC to Instance Optimality

  • The unified instance-optimality bound decomposes recovery error into exponentially decaying optimization error, signal-independent statistical error, and instance-dependent approximation error.The framework establishes E_opt(t;x)=O(ρ^t∥x∥_2) for ρ∈(0,1); statistical error vanishes in sparse phase retrieval and ReLU regression and is order O~(s/m) in one-bit compressed sensing.Source: §2.2 · p. 8

2.2.1 (Uniform) Instance Optimality

  • Uniform instance optimality splits signals into an approximately sparse class X and its complement, applying signal-dependent RAIC and initialization on X and separate analysis or regularization on X^c.For x∈X, Theorems 2.3 and 2.4 establish instance optimality for IHT and NIHT; the resulting error includes statistical term O(μ_2), signal-dependent term O(e(x)), and intrinsic sparsity-approximation term O(∥x−x_[s]∥_2).Source: §2.2.1 · pp. 9–10

2.2.2 Non-Uniform Instance Optimality

  • Non-uniform instance optimality guarantees the same error decomposition for a fixed signal, weakening uniform coverage but often permitting a sharper model-error term.The framework again treats approximately sparse signals through RAIC and handles the complement separately.Source: §2.2.2 · pp. 10–11

3 Sparse Phase Retrieval

This section introduces bounded thresholded amplitude flow (BTAF), the first efficient instance-optimal algorithm proposed for sparse phase retrieval, under Gaussian measurements. It establishes uniform instance optimality with ~O(s^3) measurements and non-uniform guarantees for fixed signals with ~O(s^2) measurements.

3.1 Algorithm

  • BTAF combines thresholded amplitude flow with an additional projection, extending iterative hard thresholding to sparse phase retrieval.Its initialization uses a truncated spectral construction, and the algorithm applies a fixed step size of 1.Source: §3.1 · pp. 11–12

3.2 Instance Optimality

  • Under ~O(s^3) Gaussian measurements, BTAF achieves uniform instance optimality for sparse phase retrieval.The analysis covers sparse or approximately sparse signals and is based on the signal-dependent RAIC and initialization guarantees.Source: §3.1 · p. 11, §3.2 · p. 13, §3.2.1 · p. 14

3.2.1 Technical Overview for Theorem 3.1

  • The uniform proof requires controlling the RAIC and initialization simultaneously over a model class, with restricted-eigenvalue bounds producing the s^3 sample complexity.The argument transfers IHT guarantees to the projected iterates and handles signals outside the model class through projection.Source: §3.2.1 · pp. 14–15

3.3 Non-Uniform Instance Optimality

  • For any fixed signal, BTAF provides non-uniform instance optimality under ~O(s^2 log n) Gaussian measurements.The fixed-signal guarantee improves the model-error term from O(τ_s(x)) to O(δ_s(x)).Source: §3.3 · p. 15
  • The ~O(s^2) non-uniform complexity matches the best-known efficient complexity for exact recovery of arbitrary s-sparse signals.This improvement follows because the RAIC and initialization bounds need only hold for the fixed signal rather than uniformly over all signals.Source: §3.3 · p. 15

4 One-Bit Compressed Sensing

For one-bit compressed sensing, the paper identifies NBIHT as an instance of its normalized iterative hard-thresholding framework and proves instance-optimal recovery under Gaussian measurements. It also establishes sharper non-uniform guarantees through an instance-dependent hyperplane tessellation analysis.

4.1 Algorithm

  • NBIHT is obtained as a specialization of NIHT using the ReLU loss, a convex relaxation of Hamming loss, for observations y = sign(Ax).The setting assumes sparse x ∈ S^{n−1} and Gaussian A.Source: §4.1 · p. 16, §4 · p. 16

4.2 Instance Optimality

  • The main theorem establishes instance optimality for NBIHT, with an unavoidable statistical error term and a model-error term carrying an extra logarithmic factor.The statistical rate is optimal up to logarithmic factors, while avoiding that extra model-error logarithm remains open.Source: §4.2 · pp. 16–17

4.2.1 Technical Overview for Theorem 4.1

  • The analysis exploits asymmetric tessellation between approximately sparse vectors and the thinner set of truncated sparse approximations, unlike prior bounds treating both arguments uniformly.This asymmetry addresses the discontinuity of sign, which prevents a simple Lipschitzness-based argument.Source: §4.2.1 · pp. 18–19
  • The proof’s key technical contribution is an instance-dependent hyperplane tessellation bound that preserves the optimal statistical error rate for approximately sparse signals.It improves the concentration error from ˜O((s/m)1/4) to a constant term ˜O(s/m), at the cost of model error ˜O(τ_s(x)).Source: §4.2.1 · p. 18

4.3 Non-Uniform Instance Optimality

  • For a fixed signal, the non-uniform guarantee removes the logarithmic loss in the model-error term and improves on the prior near-optimal uniform rate for specified approximation-error regimes.The proof removes the logarithm by decomposing the gradient into orthogonal components and concentrating each component separately.Source: §4.3 · pp. 19–20

5 Sparse ReLU Regression

This section studies recovery of an s-sparse signal from ReLU measurements and introduces bounded ReLU iterative hard thresholding (BReLUIHT). It establishes both instance-optimal and fixed-signal non-uniform recovery guarantees under Gaussian designs.

5 Sparse ReLU Regression

  • Sparse ReLU regression recovers an s-sparse x from measurements y = ReLU(Ax), where ReLU(a) = max{a, 0}.The section focuses on the sparse parameter-estimation problem arising from ReLU observations.Source: §5 · p. 20

5.1 Algorithm

  • BReLUIHT is a bounded variant of projected-gradient IHT using the ReLU-based ℓ2 loss and an additional projection to control iterates.The method uses fixed step size η = 1 and modifies the algorithm in [61].Source: §5.1 · pp. 20–21

5.2 Instance Optimality

  • For Gaussian measurements, BReLUIHT achieves instance-optimal recovery for sparse ReLU regression under a near-s log(en/s) measurement condition.The result provides the sparse ReLU analogue of the paper’s general instance-optimality guarantee.Source: §5.2 · p. 21

5.3 Non-Uniform Instance Optimality

  • For any fixed signal x, Gaussian designs yield a non-uniform instance-optimality guarantee for BReLUIHT under m ≳ s log(en/s) measurements.The theorem gives the sparse ReLU analogue of the fixed-signal guarantee, with probability controlled exponentially in s log(en/s).Source: §5.3 · p. 21

6 Conclusion · A Proofs for Convergence of IHT and NIHT

The paper develops a general signal-dependent RAIC framework for instance-optimal sparse recovery from nonlinear measurements, while the appendix proves convergence ingredients for IHT and NIHT. The framework yields guarantees for several Gaussian-design problems and identifies directions for future work.

6 Conclusion

  • Signal-dependent RAIC for a suitable gradient map provides a general route to instance optimality of IHT for nonlinear sparse recovery.The framework targets robustness to model error and connects non-uniform instance optimality to oracle inequalities.Source: §6 · p. 22
  • Gaussian-design RAICs establish instance-optimal guarantees for sparse phase retrieval, one-bit compressed sensing, and sparse ReLU regression.The framework also applies to phase-only compressed sensing, with guarantees comparable to as discussed in [14, Section 2].Source: §6 · p. 22
  • Future directions include non-Gaussian designs, sharp oracle inequalities under nonlinear observations, and tuning the sparsity level.These questions are presented as extensions of the developed framework.Source: §6 · p. 22

A Proofs for Convergence of IHT and NIHT

  • A preliminary convergence lemma controls post-hard-thresholding error using the top-2s ℓ2 norm.This lemma is used in the proofs of convergence for IHT and NIHT.Source: A Proofs for Convergence of IHT and NIHT · p. 26
  • Because H_s(u) is the best s-sparse approximation to u restricted to the union of the supports of H_s(u) and v, the proof obtains the required approximation bound.The argument compares the thresholded vector with the restriction u_T1∪T2.Source: A Proofs for Convergence of IHT and NIHT · p. 26
  • The support-restricted error satisfies ∥v − u_T1∪T2∥2 = ∥(u − v)_T1∪T2∥2 ≤ ∥u − v∥2,2s.This inequality completes the post-hard-thresholding estimate used in the convergence proof.Source: A Proofs for Convergence of IHT and NIHT · p. 26

A.1 Proofs of Theorems 2.1–2.2 (Convergence of IHT and NIHT) … C.1.2 Proof of the Initialization Guarantee (3.7)

The appendices prove contraction-based convergence for IHT and NIHT, introduce Gaussian-width and covering-number tools, and establish the sparse phase-retrieval RAIC and initialization guarantees. The proofs combine induction, Gaussian restricted-eigenvalue bounds, prior RAIC results, and rotational invariance.

A.1 Proofs of Theorems 2.1–2.2 (Convergence of IHT and NIHT)

  • The error satisfies ∥x_{t+1} − x∥2 ≤ 2qµ1∥x_t − x∥2 + 2qµ2 + 3q∥x − x[s]∥2 ≤ ρf_t + b = f_{t+1}, with f0 = ∥x0 − x∥2.Source: §A.1 · pp. 27–28
  • The convergence proof establishes the recursion by induction, using one-step estimates, the RAIC on the local region, and standard inequalities for IHT and NIHT.The induction maintains ∥xt − x∥2 ≤ ft and concludes the theorem bounds after substituting q = 1 and q = 2.Source: §A.1 · pp. 27–28

B Gaussian Width and Covering Number

  • The appendix introduces Gaussian width, covering numbers, and metric entropy as the concentration tools used in subsequent proofs.It defines Gaussian width using g ∼ N(0, I_n) and covering numbers through radius-r ℓ2-ball covers.Source: B Gaussian Width and Covering Number · p. 28

C Proofs for Sparse Phase Retrieval

  • The sparse phase-retrieval proofs restrict attention to X = {u ∈ R^n : τ_s(u) ≤ c*∥u∥2} and invoke Gaussian restricted-eigenvalue bounds.Lemma C.1 states a corresponding property for Gaussian matrices.Source: §C.1 · p. 29

C.1.1 Proof of the RAIC in (3.6)

  • The RAIC proof decomposes the target expression into terms involving u − x[s] − h_x[s](u) and h_x(u) − h_x[s](u).This decomposition is the starting point for separately controlling the sparse and tail-dependent components.Source: §C.1.1 · p. 29

(i) Bounding ∥u − x[s] − h_x[s](u)∥2s,2

  • The first RAIC component is controlled through the prior RAIC in [18, Theorem B.9], combined with Gaussian width and metric-entropy estimates.The argument uses that u and x[s] are both s-sparse and imposes sufficiently small universal constants.Source: (i) Bounding ∥u −x[s] −hx[s](u)∥2s,2 · p. 29

(ii) Bounding ∥h_x(u) − h_x[s](u)∥2s,2

  • The second RAIC component bounds h_x(u) − h_x[s](u) using tail decompositions, triangle and Cauchy–Schwarz inequalities, and a Gaussian-matrix estimate.Substitution of the resulting bounds, together with ∥x − x[s]∥2 ≤ τ_s(x), yields (C.3).Source: (ii) Bounding ∥hx(u) −hx[s](u)∥2s,2 · p. 30

C.1.2 Proof of the Initialization Guarantee (3.7)

  • The initialization guarantee is derived by analyzing the normalized signal and computing E[˜S_x] via rotational invariance, with universal constants c♭ ≈ 0.7809 and c⋄ ≈ 0.6899.The proof describes the expectation calculation as straightforward and omits its details.Source: §C.1.2 · p. 30

(iii) A Deterministic Initialization Error Bound … C.2 Proof of Theorem 3.2 (Non-Uniform Instance Optimality)

This section establishes non-uniform instance optimality by combining deterministic initialization and projection-control arguments with RAIC-based decomposition. It also shows that the projection term does not affect the iterates and handles signals outside X via a constant-order bound.

(iii) A Deterministic Initialization Error Bound

  • For nonzero signals with sufficiently small τ_s(x)/∥x∥_2, the initialization obeys dist(x_0, x) ≲ √c̄∥x∥_2.The proof uses eigengap control and Davis–Kahan perturbation bounds to compare the empirical leading eigenvector with the target direction.Source: (iii) A Deterministic Initialization… · pp. 31, 33
  • The initialization guarantee holds uniformly over X with probability at least 1 − C exp(−cs log(en/s)) when m ≳ s log(en/s) and c* is sufficiently small.The uniform argument combines concentration for empirical embeddings, truncated empirical processes, and Gaussian quadratic forms.Source: (iii) A Deterministic Initialization… · pp. 37–38

C.1.3 Projection Has No Effect on x ∈X

  • For iterates satisfying (3.8), the additional projection in Algorithm 1 has no effect on signals in X.The argument shows that the iterate norm remains below the projection radius 2λ_x.Source: §C.1.3 · p. 39

(vi) Establishing (C.43)

  • Under small enough c and c*, the bounds in (3.8) imply ∥x_t∥_2 < 2λ_x for every x ∈ X, establishing (C.43).The proof uses (C.10) to lower-bound λ_x and compares it with the iterate norm.Source: (vi) Establishing (C.43) · p. 39

C.1.4 A Separate Argument for x ∈X c

  • For x ∈ X^c, a separate argument uses the projection onto B_n(2λ_x) to obtain the desired iterate bound.The proof controls the signal norm through the definition of X^c and applies the projection directly.Source: §C.1.4 · p. 39

C.2 Proof of Theorem 3.2 (Non-Uniform Instance Optimality)

  • Theorem 3.2 is proved by decomposing R^n into X and X^c, establishing RAIC, controlling initialization, and applying the iteration argument.For X, the construction uses δ_s(u) ≤ c*∥u∥_2; initialization requires m ≳ s^2 up to logarithmic factors.Source: §C.2 · p. 40
  • The term PB_n^2(2λx) has no effect on Algorithm 1's iterates, so they satisfy (3.8).Source: §C.2 · p. 40
  • For x ∈X c, the desired error bound (3.13) reduces to a Θ(1) bound, for which a simple argument suffices.Source: §C.2 · p. 40

C.2.1 Proof of the RAIC in (C.45) if x ∈X … D.1 Proof of Theorem 4.1 (Instance Optimal 1bCS)

The proofs establish the RAIC and initialization guarantees for x ∈ X, show projection does not alter the iterates, and separately address x ∈ X^c before beginning the one-bit compressed sensing proof.

C.2.1 Proof of the RAIC in (C.45) if x ∈X

  • For x ∈ X \ {0}, the proof establishes the RAIC in (C.45) using existing bounds, triangle inequality, Cauchy–Schwarz, and Gaussian concentration.The argument combines these estimates with ∥h_x(u) − h_x[s](u)∥_2s,2 ≤ 4∥x − x[s]∥_2 to obtain (C.48).Source: §C.2.1 · pp. 40–41

C.2.2 Proof of the Initialization Guarantee (C.46) if x ∈X

  • Lemma C.4 reduces the initialization guarantee (C.46) for x ∈ X to verifying conditions (C.10)–(C.12), since (C.9) follows from sufficiently small c∗.The proof then invokes these conditions to conclude (C.46).Source: §C.2.2 · p. 41, Establishing (C.11)–(C.12) · p. 43

Establishing (C.10)

  • Under m ≳ log n, a sharper norm estimate and a sub-Gaussian tail bound establish condition (C.10).The estimate follows from ∥λx/∥x∥_2 − 1∥_ψ2 = O(m^−1/2).Source: Establishing (C.10) · p. 41

Establishing (C.11)–(C.12)

  • For fixed x ∈ X \ {0}, a product-process concentration inequality yields (C.11)–(C.12) with the promised probability when m ≳ s^2 log n.The proof exploits the fixed-x setting for tighter bounds and applies the inequality with u ≍ s log(en/s).Source: Establishing (C.11)–(C.12) · pp. 41–42

C.2.3 The Projection Has No Impact if x ∈X

  • For x ∈ X, sufficiently small constants ensure the iterates remain within B_2^n(2λ_x), so the projection in Algorithm 1 has no impact.The argument derives ∥x_t∥_2 ≤ 2λ_x for every t ≥ 0 from (C.47).Source: §C.2.3 · p. 43

C.2.4 A Separate Argument if x ∈X c

  • For x ∈ X^c, under m ≳ s^2 log n, the proof separately bounds the iterates and their distance to x to address this complementary case.It uses ∥x_t∥_2 ≤ 2λ_x ≤ 3∥x∥_2 and obtains dist(x_t, x) ≤ 4∥x − x[s]∥_2/c∗.Source: §C.2.4 · p. 43

D.1 Proof of Theorem 4.1 (Instance Optimal 1bCS)

  • For Theorem 4.1, the remaining task is to prove (4.2), which is reformulated directly from its definition under a sufficiently small c∗.The supplied proof begins by identifying this equivalence.Source: §D.1 · p. 44

D.1.1 Proof of the RAIC in (D.1) … E Proofs for Sparse ReLU Regression

The proofs establish the signal-dependent RAIC through a novel instance-dependent hyperplane tessellation, then derive non-uniform instance optimality and complete the sparse ReLU regression proof setup. They combine geometric decompositions, Gaussian sign analyses, Bernstein bounds, and existing concentration results.

D.1.1 Proof of the RAIC in (D.1)

  • A novel instance-dependent hyperplane tessellation uniformly separates signals from their best s-term approximations and supports the RAIC under Gaussian measurements.The tessellation controls the sign-disagreement count with a signal-dependent bound involving τ_s(x), under a stated measurement lower bound and high-probability event.Source: §D.1.1 · p. 45

D.2 Proof of Theorem 4.2 (Non-Uniform Instance Optimality)

  • The non-uniform instance-optimality proof decomposes the sphere into signals satisfying δ_s(x)≤c* and its complement, applying the unified theorem to the former and a crude bound to the latter.For x outside the designated set, the proof uses ∥x_t−x∥_2≤2 and obtains ∥x_t−x∥_2≤2δ_s(x)/c*.Source: §D.2 · p. 49

D.2.1 Proof of the RAIC in (D.18)

  • The RAIC in (D.18) is analyzed sharply using the two unit vectors x and x[s]/∥x[s]∥_2 and an orthogonal basis of their span.The proof decomposes each Gaussian measurement vector relative to this basis before bounding the resulting terms.Source: §D.2.1 · pp. 49–50

Bounding Ξ7 and Ξ8

  • Bounds for Ξ7 and Ξ8 rely on a moment-based Bernstein inequality together with auxiliary facts from [16].The Bernstein tool is stated for independent random variables with moment and tail parameters, while the auxiliary estimates are attributed to [16, Facts 1, 2].Source: Bounding Ξ7 and Ξ8 · p. 50

Bounding Ξ9

  • The Ξ9 estimate combines bounds derived using [65, Proposition 2.6.1] and [65, Exercise 8.6.5], completing the proof of the target bound.The resulting estimate is substituted into (D.24), then combined with (D.21), (D.22), (D.23), and (D.25).Source: Bounding Ξ9 · pp. 51–52

E Proofs for Sparse ReLU Regression

  • The sparse ReLU regression proofs define h_x(u) as in (5.1) and restrict subsequent analysis to nonzero x because the algorithm exactly recovers x=0.The zero signal is handled separately by exact recovery.Source: E Proofs for Sparse ReLU Regression · p. 52

E.1 Proof of Theorem 5.1 (Instance Optimal Sparse ReLU Regression)

The proof establishes a signal-dependent RAIC on a decomposition of R^n, verifies initialization, and uses projection control to derive instance optimality for both parts of the decomposition.

RAIC

  • The proof establishes a signal-dependent RAIC under the decomposition X = {u ∈ R^n : τ_s(u) ≤ c*∥u∥_2}, with c* sufficiently small.This verifies the framework conditions (2.9)–(2.11) for the chosen local radius and error function.Source: §E.1 · p. 52

Initialization

  • Initialization is established for sufficiently sparse signals and sufficiently small c*, allowing Theorem 2.3 to apply to Algorithm 3 without P_Bn.Source: §E.1 · p. 52
  • The proof shows that P_Bn(2∥x_0∥_2) has no effect on iterates for nonzero x ∈ X, so the initialization condition also holds for the original Algorithm 3.Source: §E.1 · p. 52

Instance Optimality for x ∈ X^c

  • For signals outside X, the proof derives instance optimality using P_Bn(2∥x_0∥_2) together with the definition of X.Source: §E.1 · p. 52

E.1.1 Proof of the RAIC in (E.2) … E.1.4 A Separate Argument for x ∈X c

The appendix proves the RAIC and initialization guarantees, then shows the projection is inactive for nonzero signals while requiring a separate projection-based argument on X^c.

E.1.1 Proof of the RAIC in (E.2)

  • The exact-sparse RAIC proof reduces the claim to Definition 2.1 and applies [18, Theorem B.10].The argument identifies the relevant set as K = Σ_n,∗ and uses a sufficiently small universal constant.Source: §E.1.1 · p. 53
  • The RAIC in (E.2) is established first for exactly sparse signals and then extended to all nonzero x by truncation and ReLU Lipschitz bounds.The extension uses the decomposition in (E.5), controls the truncated-signal terms, and invokes ∥x−x[s]∥2 ≤ τ_s(x).Source: §E.1.1 · p. 53

E.1.2 Proof of the Initialization Guarantee (E.3)

  • The initialization guarantee (E.3) holds with probability at least 1−2 exp(−c′s log en).Its proof bounds the main term using Lemma C.13, estimates (B.2) and (B.4), and a measurement condition stated as m ≳s log en.Source: §E.1.2 · p. 54

E.1.3 The Projection Has No Effect on x ∈X \ {0}

  • For x ∈ X \ {0}, the RAIC and initialization bounds imply ∥x_t−x∥2 ≤ (c+30c*)∥x∥2 for every t ≥ 0.The proof also bounds ∥x_t∥2 by (1+c+30c*)∥x∥2 when the constants are sufficiently small.Source: §E.1.3 · p. 54
  • Under these small-constant conditions, adding the projection P_Bn does not affect the iterates satisfying (E.4).Consequently, the iterates produced by Algorithm 3 also satisfy (E.4), showing the projection has no effect on nonzero x ∈ X.Source: §E.1.3 · pp. 54–55

E.1.4 A Separate Argument for x ∈X c

  • Signals x ∈ X^c are handled separately using the projection P_Bn.For these signals, the projected iterates are first shown to satisfy a projection-induced bound, followed by triangle-inequality estimates involving Lemma C.1 and (C.44).Source: §E.1.4 · p. 55

E.2 Proof of Theorem 5.2 (Non-Uniform Instance Optimality) … E.2.4 Separate Argument if x ∈X c

The proof establishes non-uniform instance optimality by splitting signals into X and X^c, proving the RAIC and initialization conditions on X, and treating X^c separately. It then shows that the projection does not alter the iterates on X while controlling iterate norms on X^c.

E.2 Proof of Theorem 5.2 (Non-Uniform Instance Optimality)

  • The proof decomposes R^n into X={u:δ_s(u)≤c*||u||_2} and its complement X^c.This split organizes separate arguments for instance optimality depending on whether the fixed signal belongs to X.Source: §E.2 · p. 55
  • Thus, the proof completes the non-uniform instance-optimality analysis by combining the X-case conditions with the separate X^c iterate bound.The X-case establishes the RAIC, initialization, and projection behavior, while X^c is addressed directly.Source: §E.2 · p. 55, §E.2.1 · p. 56, §E.2.3 · p. 56
  • The RAIC and initialization conditions allow Theorem 2.1 to yield the desired guarantee for Algorithm 3 without PB_n.The argument reuses the initialization bound from Theorem 5.1 to ensure condition (2.12).Source: §E.2 · p. 55

E.2.1 Proof of the RAIC (E.10) if x ∈X

  • For fixed nonzero x∈X, the proof establishes the restricted approximate invertibility condition (RAIC) in (E.10).The argument reuses (E.5) and (E.6), bounds the remaining term involving h_x(u)−h_x[s](u), and combines these estimates to obtain (E.12).Source: §E.2.1 · pp. 55–56

E.2.2 Proof of the Initialization Guarantee (E.11) if x ∈X

  • For x∈X, the initialization guarantee follows when m ≳ s log(en/s), provided c* is sufficiently small.The proof ensures ||x_0−x||_2≤c||x||_2 using a high-probability bound valid for fixed x and the condition δ_s(x)/||x||_2≤c*.Source: §E.2.2 · p. 56

E.2.3 The Projection Has No Effect if x ∈X

  • When x∈X, the iterates satisfy ||x_t||_2≤2||x_0||_2, so adding PB_n(2||x_0||_2) has no effect.The bound follows from Theorem 2.1, ||x_t−x||_2, and the initialization relation ||x_0||_2≥(1−c)||x||_2 under sufficiently small c and c*.Source: §E.2.3 · p. 56

E.2.4 Separate Argument if x ∈X c

  • For x∈X^c, the separate argument controls Algorithm 3’s iterates by ||x_t||_2≤2||x_0||_2≤4||x||_2+6||x−x_[s]||_2.This case is handled on the same high-probability event used in the proof, rather than through the X-specific RAIC argument.Source: §E.2.4 · p. 56

Related papers

Loading 2609.02120v1…