Perturbing a deterministic n-dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms [Spielman and Teng, JACM 2004], as it reduces the condition number of the input to O(n), and with it the complexity of many matrix algorithms. However, when deployed algorithmically, these perturbations are expensive due to the cost of generating and storing n2 Gaussian random variables. We propose a perturbation that requires generating and storing O(n) random numbers in O(logn) bits of precision, and reduces the condition number of any deterministic matrix to O(n), matching Gaussian perturbations. Our result in particular implies a better complexity for the perturbed conjugate gradient algorithm, showing that we can solve an n×n linear system in linear space to within an arbitrarily small constant backward error using O(n) matrix-vector products. In our construction, we introduce the concept of a pattern matrix, which is a dense deterministic matrix that maps all sparse vectors into dense vectors, and we combine it with a sparse perturbation whose entries are dependent and located in a non-uniform fashion. In order to analyze this construction, we develop new techniques for lower bounding the smallest singular value of a random matrix with dependent entries.
We consider the effect of Gaussian perturbations on least-squares residuals, orthogonal projections, and QR-type algorithms. The problem that motivated our investigations is as follows: suppose that a full column-rank matrix B∈Rm×n has already been computed, and suppose that a new normalized column q=(x+y)/∥x+y∥2 is to be appended to B, where x⊥span(B) is the ideal orthogonal component and y represents the orthogonalization error. How large can the condition number κ([B,q]) of the resulting matrix [B,q] become? While we provide a Weyl-type bound on the singular values of [B,q], in terms of the extremal singular values of B and the quantity ∥BTy∥2/∥x+y∥2, we also derive exact probability laws for norms and projection residuals under Gaussian perturbations. Finally, we use these probability laws to derive probabilistic condition-number bounds for QR-type processes with imperfect orthogonalization and exact normalization.
In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in sparse convex optimization cannot be improved by a polynomial-time algorithm. We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis in the weighted regular-graph formulation of Raghavendra, Steurer, and Tulsiani [RST12]. Concretely, for every fixed γ∈(0,1], there is no randomized polynomial-time algorithm that, with probability at least 2/3, returns a vector x such that, writing s=∥x∥0,
∥Ax−b∥22≤∥z∥0≤kmin∥Az−b∥22+εands=O(kκs+k1−γ),
where κr is the restricted condition number at sparsity level r. The result holds even on rational instances with A of full column rank. The proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified the proof and edited it for clarity of presentation.
This paper studies the stability of low-rank implicit regularization in perturbed deep matrix factorization, where the target matrix is corrupted by a noise matrix. We first derive sufficient spectral conditions under which gradient descent exhibits a low-rank phase in the noiseless setting. These conditions show how the target spectrum, initialization, and step size jointly determine the existence of a nonempty low-rank interval. We then analyze the perturbed gradient descent dynamics, proving convergence guarantees and quantifying how the perturbation affects iteration complexity and eigenvalue recovery. Finally, we show that the low-rank phase persists under perturbation, with explicit dependence on the perturbation size. Numerical experiments support the theoretical findings.