Atomic Norm Convex Geometry and Tangent Cone Gaussian Width for Linear Inverse Problems
Mathematical Methods AIMech:AtomicNormConvexGeometryAndTangentConeGaussianWidthForLinearInverseProblems DRAFT
Aliases: Atomic Norm Minimization and Tangent Cone Gaussian Width, Chandrasekaran-Recht-Parrilo-Willsky Atomic Norm Framework, Convex Geometry of Linear Inverse Problems via Atomic Norms, Polar Normal-Cone Distance Bound for Tangent-Cone Gaussian Width
Atomic Norm Convex Geometry and Tangent Cone Gaussian Width for Linear Inverse Problems is a unified convex-geometric framework for recovering structured models $x^\star \in \mathbb{R}^p$ that are sparse nonnegative combinations $x^\star = \sum_{i=1}^k c_i a_i$ ($c_i > 0$) of atoms from a compact atomic set $\mathcal{A} \subset \mathbb{R}^p$ (whose elements are extreme points of $\operatorname{conv}(\mathcal{A})$) from underdetermined linear measurements $y = \Phi x^\star + \omega$ ($\Phi \in \mathbb{R}^{n \times p}$). It induces the gauge (atomic norm) $\|x\|_{\mathcal{A}} = \inf\{t > 0 : x \in t\operatorname{conv}(\mathcal{A})\} = \inf\{\sum_{a \in \mathcal{A}} c_a : x = \sum_{a \in \mathcal{A}} c_a a,\, c_a \ge 0\}$ and dual support norm $\|x\|_{\mathcal{A}}^* = \sup_{a \in \mathcal{A}} \langle x, a \rangle$, characterizes exact and robust recovery via the tangent cone $T_{\mathcal{A}}(x^\star) = \operatorname{cone}\{z - x^\star : \|z\|_{\mathcal{A}} \le \|x^\star\|_{\mathcal{A}}\}$ and its polar normal cone $N_{\mathcal{A}}(x^\star) = T_{\mathcal{A}}(x^\star)^* = \operatorname{cone}(\partial \|x^\star\|_{\mathcal{A}}), and bounds the required number of random Gaussian measurements by the squared Gaussian width $w(T_{\mathcal{A}}(x^\star) \cap \mathbb{S}^{p-1})^2 \le \mathbb{E}_{g \sim \mathcal{N}(0, I_p)}[\operatorname{dist}(g, N_{\mathcal{A}}(x^\star))^2]$.
Identity Notes & Concept Scope
Distinct from specific compressed-sensing, matrix-completion, or singular-value-thresholding records (`AIMech:RestrictedIsometryPropertyForCompressedSensing`, `AIMech:NuclearNormConvexRelaxationForMatrixCompletion`, `AIMech:SingularValueThresholdingForMatrixCompletion`, `AIMech:MinimaxRiskOfMatrixDenoisingBySingularValueSoftThresholding`), which analyze a single norm ($\ell_1$ or nuclear norm) or direct matrix denoising ($\Phi = I$). Chandrasekaran, Recht, Parrilo, & Willsky (2012) formulate the general atomic-set gauge/support-function theory over arbitrary compact atomic sets $\mathcal{A}$ (unifying sparse vectors, low-rank matrices, sign vectors, orthogonal matrices, permutation matrices, and algebraic varieties), prove the polar normal-cone distance bound $w(\mathcal{C} \cap \mathbb{S}^{p-1}) \le \mathbb{E}_g[\operatorname{dist}(g, \mathcal{C}^*)]$ via Lagrangian duality, and analyze the computational-statistical sample-complexity tradeoff across semidefinite theta-body outer relaxations $\mathrm{TH}_k(I)$.
Claims & Grounded Evidence
3 Claims
Mechanism
#atomic-norm-gauge-dual-norm-and-tangent-normal-cone-recovery-characterization
For any compact atomic set $\mathcal{A} \subset \mathbb{R}^p$ whose elements are extreme points of $\operatorname{conv}(\mathcal{A})$ (with centroid at the origin), the atomic norm gauge $\|x\|_{\mathcal{A}} = \inf\{t > 0 : x \in t\operatorname{conv}(\mathcal{A})\}$ and dual norm $\|x\|_{\mathcal{A}}^* = \sup_{a \in \mathcal{A}} \langle x, a \rangle$ induce the convex optimization program $\hat{x} = \arg\min_x \|x\|_{\mathcal{A}} \text{ s.t. } y = \Phi x$; the true signal $x^\star = \sum_{i=1}^k c_i a_i$ ($c_i > 0$) is the unique optimum if and only if $\operatorname{null}(\Phi) \cap T_{\mathcal{A}}(x^\star) = \{0\}$ (equivalently $\operatorname{row}(\Phi) \cap \operatorname{relint}(N_{\mathcal{A}}(x^\star)) \ne \emptyset$), where $T_{\mathcal{A}}(x^\star) = \operatorname{cone}\{z - x^\star : \|z\|_{\mathcal{A}} \le \|x^\star\|_{\mathcal{A}}\}$ is the tangent cone and $N_{\mathcal{A}}(x^\star) = T_{\mathcal{A}}(x^\star)^* = \{s : \langle s, x^\star \rangle = t\|x^\star\|_{\mathcal{A}},\, \|s\|_{\mathcal{A}}^* \le t \text{ for some } t \ge 0\}$ is its polar normal cone, while under bounded noise $\|y - \Phi x^\star\|_2 \le \delta$ the condition $\|\Phi z\|_2 \ge \epsilon \|z\|_2$ on $T_{\mathcal{A}}(x^\star)$ guarantees $\|\hat{x} - x^\star\|_2 \le 2\delta/\epsilon$.
Mechanism
#gordon-escape-polar-normal-cone-distance-bound-and-canonical-atomic-gaussian-widths
For an i.i.d. Gaussian measurement matrix $\Phi \in \mathbb{R}^{n \times p}$ with entry variance $1/n$ and spherical tangent-cone section $\Omega = T_{\mathcal{A}}(x^\star) \cap \mathbb{S}^{p-1}$, Gordon's escape-through-a-mesh inequality guarantees exact recovery with probability at least $1 - \exp(-\frac{1}{2}[\lambda_n - w(\Omega)]^2)$ when $n \ge w(\Omega)^2 + 1$ (where $\lambda_n = \mathbb{E}_{g \sim \mathcal{N}(0, I_n)}[\|g\|_2] \ge \frac{n}{\sqrt{n+1}}$) and robust recovery $\|\hat{x} - x^\star\|_2 \le 2\delta/\epsilon$ when $n \ge \frac{w(\Omega)^2 + 3/2}{(1 - \epsilon)^2}$; by Lagrangian duality on the cone $\mathcal{C} = T_{\mathcal{A}}(x^\star)$ and its polar $\mathcal{C}^* = N_{\mathcal{A}}(x^\star)$, $w(\mathcal{C} \cap \mathbb{S}^{p-1}) \le \mathbb{E}_g[\operatorname{dist}(g, \mathcal{C}^*)]$ and $w(\mathcal{C} \cap \mathbb{S}^{p-1})^2 \le \mathbb{E}_g[\operatorname{dist}(g, \mathcal{C}^*)^2]$ (with Moreau sum-of-squares $w(\mathcal{C} \cap \mathbb{S}^{p-1})^2 + w(\mathcal{C}^* \cap \mathbb{S}^{p-1})^2 \le p$ and $w(\mathcal{C} \cap \mathbb{S}^{p-1})^2 \le p/2$ for self-dual cones), yielding explicit non-asymptotic sample complexity thresholds: $2s\log(p/s) + \frac{5}{4}s + 1$ for $s$-sparse vectors in $\mathbb{R}^p$ ($\ell_1$ norm), $3r(m_1 + m_2 - r) + 1$ for $m_1 \times m_2$ rank-$r$ matrices (nuclear norm), $\frac{p+k}{2}$ for sign vectors on a $k$-face ($\ell_\infty$ norm), $\frac{3m^2 - m}{4}$ for $m \times m$ orthogonal matrices (spectral norm), and $9m\log m$ for $m \times m$ permutation matrices (Birkhoff polytope).
Scope
#theta-body-semidefinite-relaxations-terracini-secant-lower-bounds-and-moreau-proximal-decomposition
When the atomic set $\mathcal{A} = V_{\mathbb{R}}(I)$ is the real algebraic variety of a polynomial ideal $I \subset \mathbb{R}[x]$ whose convex hull is computationally intractable, the $k$-th semidefinite theta body $\mathrm{TH}_k(I) = \{x \in \mathbb{R}^p : f(x) \ge 0 \text{ for all linear } f \text{ that are } k\text{-sos modulo } I\}$ forms an outer relaxation hierarchy $\operatorname{conv}(V_{\mathbb{R}}(I)) \subseteq \cdots \subseteq \mathrm{TH}_{k+1}(I) \subseteq \mathrm{TH}_k(I)$ whose enlarged tangent cones quantify the tradeoff between computational tractability and measurement complexity (requiring $\mathcal{O}(m)$ Gaussian measurements for $m \times m$ rank-1 cut matrices under both the cut polytope $\mathcal{P}$ and elliptope SDP relaxation $\mathcal{P}_1 = \mathrm{TH}_2(I)$, versus $\frac{m^2 - m}{4}$ measurements under the box relaxation $\mathcal{P}_2$); moreover, Terracini's Lemma on the $(k-1)$-th secant variety tangent space $\mathcal{T}(a_1, \mathcal{A}) \oplus \cdots \oplus \mathcal{T}(a_k, \mathcal{A}) \subset T_{\mathcal{A}}(x^\star)$ establishes relaxation-independent measurement lower bounds, and Moreau decomposition splits any $x = \Pi_{\mathcal{A}}(x; \mu) + \Lambda_{\mathcal{A}}(x; \mu)$ into the atomic-norm proximity operator $\Pi_{\mathcal{A}}(x; \mu) = \arg\min_y \frac{1}{2}\|x - y\|_2^2 + \mu \|y\|_{\mathcal{A}}$ and the dual-norm ball projection $\Lambda_{\mathcal{A}}(x; \mu) = \arg\min_z \{\|x - z\|_2 : \|z\|_{\mathcal{A}}^* \le \mu\}$.
⚠️ Curated Limitations & Negative Results
- Non-asymptotic sample complexity guarantees via Gordon's theorem (Theorem 3.2 and Corollary 3.3) require the measurement operator $\Phi \in \mathbb{R}^{n \times p}$ to have i.i.d. zero-mean Gaussian entries (or sub-Gaussian ensembles satisfying an equivalent tangent-cone restricted minimum singular value condition); structured deterministic or Fourier sensing matrices require problem-specific incoherence or restricted isometry analyses.
- While the polar normal-cone distance bound $w(\mathcal{C} \cap \mathbb{S}^{p-1}) \le \mathbb{E}_g[\operatorname{dist}(g, \mathcal{C}^*)]$ (Proposition 3.6) is tight enough to yield sharp leading constants for $\ell_1$ and $\ell_\infty$ cones, for non-polyhedral cones or higher-level theta-body SDP relaxations $\mathrm{TH}_k(I)$ choosing an analytical subgradient multiplier in $N_{\mathcal{A}}(x^\star)$ yields an upper bound rather than the exact phase-transition threshold later characterized by the conic statistical dimension $\delta(T_{\mathcal{A}}(x^\star)) = \mathbb{E}_g[\|\Pi_{T_{\mathcal{A}}(x^\star)}(g)\|_2^2]$.
- Primary-source typographical audit of `arXiv:1012.0621v3` (`DOI:10.1007/s10208-012-9135-7`): (1) on p. 17, Proposition 3.12 line 1 writes $\mathcal{A} \in \{-1, +1\}^p$ instead of $\mathcal{A} = \{-1, +1\}^p$; (2) on p. 21, Section 4.2 first display writes $\mathrm{TH}_k(V_{\mathbb{R}}(I))$ instead of $\mathrm{TH}_k(I)$; (3) on p. 22, Section 4.3 first display writes $\forall i = 1, \dots, p$ instead of $\forall i = 1, \dots, m$ for $m \times m$ symmetric matrices $M$; (4) on p. 24, the proof of Proposition 4.5 writes $\sum_{i=2}^k c_2 a_i$ instead of $\sum_{i=2}^k c_i a_i$, and Proposition 4.6 (Terracini's Lemma) writes $\min\{p, (k+1)\dim(\mathcal{A}) + k\}$ instead of $\min\{p, k\dim(\mathcal{A}) + k - 1\}$ for the $(k-1)$-th secant variety spanned by $k$ atoms; and (5) on p. 25, Equation (21) writes $\alpha_k \lambda$ instead of $\alpha_k \mu$ for $\min_x f(x) + \mu \|x\|_{\mathcal{A}}$ in Equation (20), while Appendix C Equation (61) on p. 33 writes $|u_i| < t$ instead of $|u_i| \le t$.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:LassoRegression
Lasso Regression
|
narrow_match | Lasso / l1 basis pursuit is the canonical finitely generated specialization of atomic-norm linear inverse recovery when the atomic set is the cross-polytope vertices A = {+- e_i}_{i=1}^p. |
AIO:DimensionalityReduction
Dimensionality Reduction
|
related_match | Atomic-norm recovery reconstructs low-complexity models from low-dimensional random linear projections y = Phi x* (n << p) and encompasses nuclear-norm low-rank matrix recovery. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
crpw2012-atomic-norm-pdf
|
Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, Alan S. Willsky
|
primary paper
full_text
|
ID: https://arxiv.org/abs/1012.0621v3
sha256:5e5e4b5dc3ff…
|
crpw2012-atomic-norm-abs
|
Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, Alan S. Willsky
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/1012.0621
sha256:a03d09433b93…
|
crpw2012-atomic-norm-cr
|
Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, Alan S. Willsky
|
primary paper
abstract_only
|
ID: https://doi.org/10.1007/s10208-012-9135-7
sha256:7bc6a0d619a1…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T01:32:00Z
Updated: 2026-10-19T01:32: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