Corrupted Sensing Convex Signal-Corruption Demixing and Subdifferential Distance Bounds
Mathematical Methods AIMech:CorruptedSensingConvexSignalCorruptionDemixingAndSubdifferentialDistanceBounds DRAFT
Aliases: Corrupted Sensing Signal-Corruption Separation via Convex Programming, Foygel-Mackey Constrained and Penalized Corrupted Sensing Guarantees, Dense-Regime Subdifferential Gaussian Distance Bounds for Structured Norms, Weak Decomposability Subdifferential-to-Tangent-Cone Gaussian Width Gap Bound
Corrupted Sensing Convex Signal-Corruption Demixing and Subdifferential Distance Bounds is a convex recovery and Gaussian-width analysis framework introduced by Foygel and Mackey (2014, IEEE Transactions on Information Theory 60(2):1223-1247, DOI:10.1109/TIT.2013.2293654, arXiv:1305.2524v2) for simultaneously recovering a structured signal $x^\star \in \mathbb{R}^p$ (with atomic norm $\|\cdot\|_{\text{sig}}$) and structured measurement corruption $v^\star \in \mathbb{R}^n$ (with atomic norm $\|\cdot\|_{\text{cor}}$) from noisy underdetermined Gaussian linear observations $y = \Phi x^\star + v^\star + z$ ($\Phi_{ij} \stackrel{\text{i.i.d.}}{\sim} \mathcal{N}(0, 1/n)$, $\|z\|_2 \le \delta$). It proves non-asymptotic recovery error bounds $\sqrt{\|\hat{x} - x^\star\|_2^2 + \|\hat{v} - v^\star\|_2^2} \le 2\delta/\epsilon$ for both norm-constrained convex programs (requiring $\mu_n > \tau = \sqrt{\omega^2(T_{\text{sig}} \cap \mathbb{B}^p) + \omega^2(T_{\text{cor}} \cap \mathbb{B}^n)} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{2\pi}}$, Theorems 1 & 3) and penalized convex programs $\min_{x,v}\{\|x\|_{\text{sig}} + \lambda\|v\|_{\text{cor}} : \|y - (\Phi x + v)\|_2 \le \delta\}$ with penalty multiplier $\lambda = t_{\text{cor}} / t_{\text{sig}}$ (requiring $\mu_n > \tau = 2\eta(t_{\text{sig}} \cdot \partial\|x^\star\|_{\text{sig}}) + \eta(t_{\text{cor}} \cdot \partial\|v^\star\|_{\text{cor}}) + 3\sqrt{2\pi} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{2\pi}}$, where $\eta(S) = \sqrt{\mathbb{E}[\operatorname{dist}(g, S)^2]}$, Theorems 2 & 4), and derives dense-regime subdifferential distance bounds strictly below ambient dimension $p$ for $\ell_1$, block-sparse $\ell_1/\ell_2$, and matrix nuclear norms (Propositions 3-5).
Identity Notes & Concept Scope
Distinct from standard uncorrupted atomic-norm linear inverse recovery (`AIMech:AtomicNormConvexGeometryAndTangentConeGaussianWidthForLinearInverseProblems`), conic kinematic demixing under random orthogonal transformations $z_0 = x_0 + U y_0$ (`AIMech:ConicStatisticalDimensionIntrinsicVolumeConcentrationAndPhaseTransitions`), and proximal denoising / uncorrupted projected LASSO risk (`AIMech:WorstCaseProximalDenoisingNMSEAndSubdifferentialMeanSquaredDistance`). Foygel & Mackey (2014) specifically analyze the asymmetric Gaussian sensing-plus-direct-corruption model $y = \Phi x^\star + v^\star + z$ ($\Phi \in \mathbb{R}^{n \times p}$, $v^\star \in \mathbb{R}^n$), establish universal penalized demixing guarantees with explicit penalty ratio $\lambda = t_{\text{cor}}/t_{\text{sig}}$ without requiring knowledge of $\|x^\star\|_{\text{sig}}$ or $\|v^\star\|_{\text{cor}}$, prove the weak-decomposability gap bound $\min_{t \ge 0}\eta(t \cdot \partial\|x\|) \le \omega(T \cap \mathbb{B}^p) + 6$ (Proposition 1), and derive dense-regime subdifferential squared-distance bounds strictly below $p$ via dual-norm Gaussian widths (Propositions 3-5).
Claims & Grounded Evidence
3 Claims
Mechanism
#constrained-and-penalized-corrupted-sensing-demixing-theorems-via-gordon-lemma
Given observations $y = \Phi x^\star + v^\star + z \in \mathbb{R}^n$ with $\Phi_{ij} \stackrel{\text{i.i.d.}}{\sim} \mathcal{N}(0, 1/n)$ and $\|z\|_2 \le \delta$, any solution $(\hat{x}, \hat{v})$ to the constrained convex program $\min_{x,v}\{\|x\|_{\text{sig}} : \|v\|_{\text{cor}} \le \|v^\star\|_{\text{cor}},\, \|y - (\Phi x + v)\|_2 \le \delta\}$ (or the symmetric program swapping $\|x\|_{\text{sig}}$ and $\|v\|_{\text{cor}}$) satisfies $\sqrt{\|\hat{x} - x^\star\|_2^2 + \|\hat{v} - v^\star\|_2^2} \le 2\delta/\epsilon$ with probability at least $1 - e^{-(\mu_n - \tau - \epsilon\sqrt{n})^2/2}$ whenever $\mu_n - \epsilon\sqrt{n} > \tau = \sqrt{\omega^2(T_{\text{sig}} \cap \mathbb{B}^p) + \omega^2(T_{\text{cor}} \cap \mathbb{B}^n)} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{2\pi}}$ (Theorem 1, p. 4; Theorem 3, p. 12; Lemma 1, p. 13). For the tuning-free penalized program $\min_{x,v}\{\|x\|_{\text{sig}} + \lambda\|v\|_{\text{cor}} : \|y - (\Phi x + v)\|_2 \le \delta\}$ with penalty multiplier $\lambda = t_{\text{cor}}/t_{\text{sig}}$ ($t_{\text{sig}}, t_{\text{cor}} > 0$), the same error bound holds with $\tau = 2\eta(t_{\text{sig}} \cdot \partial\|x^\star\|_{\text{sig}}) + \eta(t_{\text{cor}} \cdot \partial\|v^\star\|_{\text{cor}}) + 3\sqrt{2\pi} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{2\pi}}$ where $\eta(S) = \sqrt{\mathbb{E}_{g \sim \mathcal{N}(0, I)}[\operatorname{dist}(g, S)^2]}$ (Theorem 2, p. 4; Theorem 4, p. 14; Lemma 2, p. 15).
Mechanism
#dual-norm-subdifferential-squared-distance-recipe-and-dense-regime-bounds-for-l1-block-sparse-and-nuclear-norms
For any atomic norm $\|\cdot\|$ on $\mathbb{R}^p$ whose subdifferential at $x$ contains $e + \{z \in S^\perp : \|z\|^* \le 1\}$ with $e \in S$, $\|e\|_2 = 1$, and $\tilde{\omega} \le \omega(S^\perp \cap \{z : \|z\| \le 1\})$, choosing $t = \frac{\tilde{\omega}}{\max_{\|z\|_2=1}\|z\|^2}$ guarantees $\eta^2(t \cdot \partial\|x\|) \le p - \left(\frac{\tilde{\omega}}{\max_{\|z\|_2=1}\|z\|}\right)^2 < p$ whenever $x$ is non-trivial (Proposition 3, p. 17, Appendix A, p. 20). Specializing Proposition 3 and direct tail integration yields dense-regime subdifferential squared-distance bounds strictly below $p$: (1) for an $s$-sparse vector in $\mathbb{R}^p$ ($\|\cdot\|_1$), $\eta^2(t'\partial\|x\|_1) \le p\!\left(1 - \frac{2}{\pi}(1 - s/p)^2\right)$ at $t' = \sqrt{\frac{2}{\pi}}(1 - s/p)$ (Eqs. 9, 23), which is strictly tighter than $2s\log(p/s) + \frac{3}{2}s$ (Eq. 8) for all $s/p \ge 0.07$; (2) for an $s$-block-sparse vector in $\mathbb{R}^p$ with $m$ blocks of size $k = p/m$ ($\|\cdot\|_{\ell_1/\ell_2}$), $\eta^2(t\partial\|x\|_{\ell_1/\ell_2}) \le 4s\log(m/s) + (0.5 + 3k)s$ at $t = \sqrt{2\log(m/s)} + \sqrt{k}$ (Eq. 24) and $\eta^2(t'\partial\|x\|_{\ell_1/\ell_2}) \le p\!\left(1 - \frac{\mu_k^2}{k}(1 - s/m)^2\right)$ at $t' = \mu_k(1 - s/m)$ (Proposition 4, Eq. 25, pp. 17-19); and (3) for a rank-$r$ matrix in $\mathbb{R}^{m_1 \times m_2}$ ($m_1 \ge m_2$, $\|\cdot\|_*$), $\eta^2(t\partial\|x\|_*) \le m_1 m_2\!\left(1 - \left(\frac{4}{27}\right)^2\left(1 - \frac{r}{m_1}\right)\left(1 - \frac{r}{m_2}\right)^2\right)$ at $t = \frac{4}{27}(m_2 - r)\sqrt{m_1 - r}/m_2$ (Proposition 5, p. 19).
Scope
#weak-decomposability-gap-bound-and-canonical-corrupted-sensing-corollaries
For any weakly decomposable norm $\|\cdot\|$ on $\mathbb{R}^p$ whose subdifferential at $x$ contains $e + \{z \in S^\perp : \|z\|^* \le 1\}$ for some subspace $S$ and $e \in S$ with $\|e\|_2 = 1$, the minimum subdifferential Gaussian distance is within an additive constant of the tangent-cone Gaussian width: $\min_{t \ge 0} \eta(t \cdot \partial\|x\|) \le \omega(T \cap \mathbb{B}^p) + 6$ (Proposition 1, pp. 4, 20-21). Applied to canonical demixing problems, Theorems 1-2 yield: (1) recovery of $s$-sparse signals under $\gamma n$ gross sparse corruptions and Wyner real-valued coding of arbitrary $x^\star \in \mathbb{R}^p$ from $n = 2p + o(p)$ measurements up to corruption fraction $\gamma_0 \approx 19.3\%$ where $\omega^2(T_{\text{sparse}(n,\gamma_0)} \cap \mathbb{B}^n) = n/2$ (Corollary 1, pp. 7-8); (2) recovery of sparse signals under block-sparse adversarial corruptions up to corruption fraction $\gamma \to 1$ as $n/p \to \infty$ (Corollary 2, p. 9); (3) rank-$r$ matrix recovery under sparse corruptions (Corollary 3, pp. 9-10); and (4) package-clipped $\ell_\infty$-structured signal recovery under sparse outliers (Corollary 4, pp. 10-12).
⚠️ Curated Limitations & Negative Results
- Non-asymptotic recovery guarantees (Theorems 1-4) require the sensing matrix $\Phi \in \mathbb{R}^{n \times p}$ to have i.i.d. $\mathcal{N}(0, 1/n)$ entries so that Gordon's Lemma (Fact 1) applies to the joint signal-corruption cone, and assume that the corruption $v^\star$ enters in the standard observation basis ($y = \Phi x^\star + v^\star + z$) incoherent with the Gaussian rows of $\Phi$.
- While the penalized program (6) eliminates the need to know $\|x^\star\|_{\text{sig}}$ or $\|v^\star\|_{\text{cor}}$, choosing the penalty parameter $\lambda = t_{\text{cor}}/t_{\text{sig}}$ still requires estimates of the structural complexity levels (such as signal sparsity $s/p$ or rank $r$ and corruption fraction $\gamma$), and Theorem 2 incurs a factor-of-2 looser signal threshold ($2\eta(t_{\text{sig}} \cdot \partial\|x^\star\|_{\text{sig}}) + \eta(t_{\text{cor}} \cdot \partial\|v^\star\|_{\text{cor}})$ vs. $\sqrt{\omega_{\text{sig}}^2 + \omega_{\text{cor}}^2}$ in Theorem 1).
- Primary-source typographical audit of `arXiv:1305.2524v2`: (1) Section I.A (p. 2, display after Eq. 4) writes $\|v\|_{\text{sig}} \le \|v^\star\|_{\text{cor}}$ instead of $\|v\|_{\text{cor}} \le \|v^\star\|_{\text{cor}}$; (2) Table II (p. 6, row 2, column 4) prints $\frac{\mu_k}{\sqrt{k}}(1 - s/m)$ for the block-sparse setting of $t'$, whereas Proposition 4 (p. 17, after Eq. 25), Section IV.B (p. 8), and Corollary 2 (p. 9) prove $t' = \mu_k(1 - s/m)$; (3) Proposition 3 statement (pp. 17, 20) prints $t = \frac{\tilde{\omega}}{\max_{\|z\|_2=1}\|z\|}$ in the theorem statement, whereas the proof on p. 20 (final display of proof of Proposition 3) shows $t = \frac{\tilde{\omega}}{\max_{\|w\|_2=1}\|w\|^2}$ (squared norm in the denominator); (4) Corollary 1 (p. 8) prints $\mu_n - 2\delta > \tau$ and $1 - e^{-(\mu_n - 2\delta - \tau)^2/2}$ instead of $\mu_n - 2\delta\sqrt{n} > \tau$ and $1 - e^{-(\mu_n - 2\delta\sqrt{n} - \tau)^2/2}$ as derived in Appendix B.A (p. 21); (5) Proof of Proposition 4 (p. 18, col. 2) quotes the Laurent-Massart $\chi_k^2$ tail bound first with $2\sqrt{k}c + c^2$ and four lines later with $\sqrt{2k}c + c^2$; and (6) Proof of Lemma 1 (p. 26, line 6) writes 'singular values of $h$' instead of 'singular values of $\Upsilon$'.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:LassoRegression
Lasso Regression
|
related_match | Encompasses l_1-penalized and l_1-constrained sparse signal recovery in the presence of structured sparse or block-sparse measurement corruptions. |
AIO:DimensionalityReduction
Dimensionality Reduction
|
broad_match | Separates low-complexity signals (sparse vectors, block-sparse vectors, low-rank matrices) from structured corruptions in compressed Gaussian linear projections. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
fm2014-corrupted-sensing-pdf
|
Rina Foygel, Lester Mackey
|
primary paper
full_text
|
ID: https://doi.org/10.1109/TIT.2013.2293654
sha256:3f7939a1f07f…
|
fm2014-corrupted-sensing-abs
|
Rina Foygel, Lester Mackey
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/1305.2524
sha256:ded58f7c0c63…
|
fm2014-corrupted-sensing-crossref
|
Rina Foygel, Lester Mackey
|
primary paper
abstract_only
|
ID: https://doi.org/10.1109/TIT.2013.2293654
sha256:04d13fb8716f…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T02:28:00Z
Updated: 2026-10-19T02:28:00Z
Explore across X-Mech
Related computational & biological Mechs:
Embedding Map
Network Graph
ProteinTraitsMech (ESM-2 pLM)
DUFMech (Domain pLM)
TraitMech
CultureMech
All 14 X-Mech Repositories