Smooth analysis of the condition number and the least singular value

1. Introduction

• Discrete perturbations motivate the broader model because real inputs and digital errors can be discrete, and practical data may be truncated.The passage gives Bernoulli entries taking values ±1 with probability half as a toy example.Source: §1 · p. 2
• The paper generalizes the Spielman–Teng model by studying M + N_n when N_n has independent entries with arbitrary, not necessarily Gaussian, distributions.The motivating question is to estimate the condition number for a fixed M and a general random perturbation.Source: §1 · pp. 2–3
• Under stated assumptions on M and the entries of N_n, M + N_n is well-conditioned with high probability.The paper says this result extends and bridges existing results.Source: §1 · pp. 3–4
• The analysis formulates most results as tail bounds for the least singular value of M + N_n to establish typical well-conditioning.The paper notes that under its stated assumption, showing the least singular value is sufficiently large with high probability suffices.Source: §1 · p. 4

2. Previous results

• The Gaussian literature includes Edelman’s limiting-distribution result and Sankar, Spielman, and Teng’s bounds for M + N_n.For the Gaussian model, the paper notes the relation B = A + 1/2 is simple and optimal.Source: §2 · p. 4, §3 · p. 5
• For non-Gaussian entries, Komlós first proved positivity with probability 1−o(1) for Bernoulli matrices [14], and later work obtained n^-Θ(1) lower bounds with high probability.Source: §2 · p. 4
• Earlier results include a subgaussian estimate [21, Theorem 1.2] and a more general estimate for nonzero-variance entries and ∥M∥≤n^C [29, Theorem 2.1]; the latter’s parameter dependence is too generous.The paper presents Theorem 3.2 as improving that dependence and extending both earlier results.Source: §2 · pp. 4–5

3. Main result

• A Bernoulli example shows the Gaussian relation B = A + 1/2 need not hold generally, and that ∥M∥ should affect least-singular-value tail bounds.The example takes n even and constructs M with ∥M∥=L for any L≥n; the evenness assumption can be removed.Source: §3 · pp. 5–6
• Theorem 3.2 treats mean-zero entries with bounded second moment when ∥M∥≤n^γ for γ≥1/2, giving a least-singular-value estimate parameterized by A and γ.The entries of N_n are iid copies of x, and the constant may depend on x, γ, and A.Source: §3 · p. 6
• For subgaussian entries and ∥M∥=O(n^1/2), Corollary 3.6 matches Theorem 2.3 up to a loss of n^o(1).Corollary 3.5 also gives an estimate for deterministic M with ∥M∥≤n^γ.Source: §3 · p. 7
• With bounded fourth moment and ∥M∥=O(n^1/2), almost surely s_n(M_n)≥n^-1/2+o(1), matching the M=0 case of [21, Theorem 1.1] up to o(1).Corollary 3.7 covers deterministic M with ∥M∥=n^O(1).Source: §3 · p. 7
• For iid mean-zero, variance-one entries, Corollary 3.8 yields s_n(N_n)≥n^-1-o(1) almost surely.The paper notes that better estimates on ∥N_n∥ can yield better bounds on s_n.Source: §3 · p. 8

4. Theorem 3.1: The influence of M

• M is formed by adding a zero first row to M′, which concatenates L I_(n−1) with an all-L column.The construction sets L ≥ n.Source: §4 · p. 8
• For the Bernoulli perturbation, the argument considers a unit normal vector to the rows of M′_n, formed from the last n−1 rows of M_n.Source: §4 · pp. 8–9

5. Controlled moment

• A complex random variable is κ-controlled when it satisfies the stated upper bound for all complex z and w.The section uses this condition to quantify control of the second moment.Source: §5 · p. 10
• The condition requires substantial variance within |x| ≤ κ and includes phase information about the covariance of Re(x) and Im(x).A symmetric ±1 Bernoulli variable has 1-controlled second moment.Source: §5 · p. 10
• For any complex random variable with finite, nonzero variance, some phase rotation makes it κ-controlled for some κ ≥ 1 [29, Lemma 2.4].Source: §5 · p. 10
• Because phase rotation does not affect Theorem 3.2, the analysis assumes without loss of generality that x is κ-controlled, enabling estimates from.Source: §5 · p. 10
• The Theorem 3.2 estimates depend on κ, not otherwise on x’s precise distribution; the paper focuses on iid entries while noting a possible extension to independent, non-identically distributed entries sharing κ.The extension is described as likely rather than established.Source: §5 · p. 10

Section overview

• The section’s small-ball estimates apply to sums of independent variables with arbitrary coefficients and provide bounds for the event that a random matrix sends a fixed unit vector to a small vector.The opening frames these bounds as tools for studying probabilities P(|ξ1v1 + · · · + ξnvn − z| ≤ ε).Source: §6 · p. 10

Lemma 6.2 and Corollary 6.3

• For κ-controlled independent variables, the section establishes properties of associated norms and derives a crude small-ball bound uniform over z and unit coefficient vectors.The norm properties include symmetry and a triangle inequality.Source: §6 · p. 11

Theorem 6.4

• Theorem 6.4 gives a probability bound for (M + N_n)v to have small norm, for every unit vector v and deterministic matrix M, when the independent entries are κ-controlled.Its proof uses a small-ball bound for each translated row and a Chernoff inequality.Source: §6 · p. 12

Lemma 6.7

• For ρ above a constant multiple of n^-1/2, Lemma 6.7 shows that very rich vectors are approximable by sparse vectors; the parameter dependence is sharp up to constants.The section illustrates sharpness in the Bernoulli case and in the Gaussian case.Source: §6 · pp. 12–13

Theorem 6.8

• Theorem 6.8 bounds the size of a finite set that approximates every rich vector in Sε,ρ within ε in the infinity norm [29].The set size is at most n^-(1/2-o(1))nρ^-n + exp(o(n)).Source: §6 · p. 14

Preliminary reductions

• The proof assumes x is κ-controlled, with implied constants depending on κ, γ, and A, and reduces the target event to compressible and incompressible vector cases.If F holds, at least one of FComp and FIncomp holds; the two corresponding lemmas imply Theorem 3.2.Source: §7 · pp. 14–15
• P(|x| ≥ n^γ) ≤ n^(-A-2+o(1)) follows from the norm bounds and independence of the n² iid entries.The proof uses ∥Nn∥ ≥ sup_{i,j}|xij| to obtain the bound.Source: §7 · p. 14
• Lemma 7.1 gives the compressible-vector bound, while Lemma 7.2 gives the incompressible-vector bound; their proof constants may depend on β.Lemma 7.1 is proved in the next section; the more involved proof of Lemma 7.2 occupies the rest of the paper.Source: §7 · p. 15

8. Treatment of compressible vectors

• If FComp and G occur, a unit vector v has ||M_n v|| <= n^(-(2A+1)gamma) and lies within b of a unit vector supported on at most a n coordinates.This reduces the event to controlling vectors close to sparse vectors.Source: §8 · p. 15
• The unit vectors with at most a n nonzero coordinates admit a finite b-net, using the standard bound on the size of a delta-net.The net lets the argument replace the sparse-vector family by finitely many candidates.Source: §8 · p. 15
• For sufficiently small beta, the union-bound estimate is less than exp(-c'n/2), concluding the proof of Lemma 7.1.The argument applies the fixed-vector estimate from Theorem 6.4 for beta <= c/3 before taking the union bound.Source: §8 · pp. 15–16

9. Treatment of incompressible vectors

• A slight extension of a lemma from [21] allows an arbitrary event E in a bound involving each row’s distance from the span of the other rows.The proof cites [21, Lemma 3.5] and notes that its argument still works with E included.Source: §9 · p. 16
• After translating by the deterministic nth row of M, the conditional probability that X_n is not in S_{ε,ρ} is bounded by ρ = n^(-A+α).Here X is a length-n random vector with iid coordinates distributed as x.Source: §9 · p. 16
• A union bound reduces the proof to establishing the stated lemmas, including Lemma 9.2 for 0 ≤ j < J when α1 is sufficiently small.The passage specifies that α1 depends on α, A, and J, but not on n or γ.Source: §9 · p. 17

10. Proof of Lemma 9.2

• Theorem 6.8 gives a set N of unit vectors whose ε_j-neighborhoods in l∞ cover every vector in S_{ε_j,ρ_j}.The passage also states that N has a cardinality bound, but its value is not present in the supplied text.Source: §10 · p. 17
• Lemma 10.1 is proved by truncating the iid variables at n^γ and applying the moment method, using their bounded second moments and higher-moment bounds.The truncation changes the event only with probability O(n^-A); the moment estimate uses γ ≥ 1/2 and k sufficiently large compared with A/α_1.Source: §10 · p. 18
• Combining Lemma 10.1 with the approximation and triangle inequality reduces the bound to many small inner products, whose probabilities and estimate (24) yield the claim.If the norm is at most n^(1/2)n^-α_1ε_{j+1}, at least n − O(n^(1−2α_1)) of the inner products are at most ε_{j+1}; each such event has probability O(ρ_{j+1}).Source: §10 · p. 18

11. Proof of Lemma 9.3

• The proof notes a relation between (22) and (20).Source: §11 · p. 18
• The proof proceeds as in Section 8 to handle Comp(O(1) when α1 is sufficiently small.Source: §11 · p. 19
• For each u ∈ N, the proof concludes the claim using Corollary 6.3 or a minor modification of Theorem 6.4.The passage states that α1 is sufficiently small before invoking these results.Source: §11 · p. 19

• The gap can be fixed at the cost of worsening the earlier paper’s main-theorem bound by a factor of n^(gamma-1/2).Source: ERRATUM TO “SMOOTH ANALYSIS OF THE… · p. 21

1. Introduction

• An unjustified implication in ’s Section 11 requires modifying Theorem 3.2 and Corollaries 3.3, 3.5, 3.7, and 3.8.The authors thank Nick Cook for alerting them to the gap and regret the oversight.Source: §1 · p. 21
• The repaired argument weakens the lower bound on s_n(M_n) by a factor of n^{-(γ-1/2)}; the change does not affect γ = 1/2 but degrades the exponent for γ > 1/2.The authors note that, in the applications of they know of, the precise exponent for γ > 1/2 is not important to the analysis.Source: §1 · p. 21
• The erratum revises expressions in Sections 7–9 and Section 11, including adding a factor of n^{-(γ-1/2)} and requiring the event G in the Section 11 argument.It also changes the Section 11 justification to rely on the preceding section’s arguments and replaces a reference to Corollary 6.3 with Theorem 6.4.Source: §1 · p. 22
• The weakening also changes the stated bounds in Corollaries 3.3, 3.5, 3.7, and 3.8, while Corollary 3.6 remains unchanged.The erratum lists revised expressions for these corollaries, including bounds involving n and ∥M∥.Source: §1 · p. 22

2 A−A2 should now be n−3

• The second section records minor typos in, including a wording correction in Theorem 3.4 and deletion of a display in Section 4.Theorem 3.4 should say “fourth moment bounded by B”; the Section 4 display should be deleted and replaced by a period.Source: §2 · p. 22