The matrix recovery (completion) problem, a central problem in data science, involves recovering a matrix $A$ from a relatively small random set of entries. While such a task is generally impossible, it has been shown that one can recover $A$ exactly in polynomial time, with high probability, under three basic and necessary assumptions: (1) the rank of $A$ is very small compared to its dimensions (low rank), (2) $A$ has delocalized singular vectors (incoherence), and (3) the sample size is sufficiently large. Various algorithms address this task, including convex optimization by Candes, Recht, and Tao (2009, 2010), alternating projection by Hardt and Wooters (2014), and low-rank approximation with gradient descent by Keshavan, Montanari, and Oh (2009, 2010). In applications, Candes and Plan (2009) noted that it is more realistic to assume noisy observations. In such cases, the above approaches provide approximate recovery with small root mean square error, which is difficult to convert into exact recovery. Recently, results by Abbe et al. (2017) and Bhardwaj et al. (2023) on approximation in the infinity norm showed that one can recover $A$ even in the noisy case, provided $A$ has bounded precision. However, beyond the three basic assumptions, they either required that the condition number of $A$ be small (2017) or that the gaps between consecutive singular values be large (2023). These additional assumptions conflict, with one requiring singular values to be close together and the other suggesting they should be far apart. It is thus natural to conjecture that neither is necessary. In this paper, we demonstrate that this is indeed the case. We propose a simple algorithm for exact recovery of noisy data, relying solely on the three basic assumptions. The core step of the algorithm is a straightforward truncated singular value decomposition, which is highly efficient. To analyze the algorithm, we prove a new infinity norm version of the classical Davis-Kahan perturbation theorem, improving an earlier result in (2023). Our proof employs a combinatorial contour integration argument and is entirely distinct from all previous approaches.

A central challenge in machine learning is to understand how noise or measurement errors affect low-rank approximations, particularly in the spectral norm. This question is especially important in differentially private low-rank approximation, where one aims to preserve the top-$p$ structure of a data-derived matrix while ensuring privacy. Prior work often analyzes Frobenius norm error or changes in reconstruction quality, but these metrics can over- or under-estimate true subspace distortion. The spectral norm, by contrast, captures worst-case directional error and provides the strongest utility guarantees. We establish new high-probability spectral-norm perturbation bounds for symmetric matrices that refine the classical Eckart--Young--Mirsky theorem and explicitly capture interactions between a matrix $A \in \mathbb{R}^{n \times n}$ and an arbitrary symmetric perturbation $E$. Under mild eigengap and norm conditions, our bounds yield sharp estimates for $\| (A + E)_p - A_p \|$, where $A_p$ is the best rank-$p$ approximation of $A$, with improvements of up to a factor of $\sqrt{n}$. As an application, we derive improved utility guarantees for differentially private PCA, resolving an open problem in the literature. Our analysis relies on a novel contour bootstrapping method from complex analysis and extends it to a broad class of spectral functionals, including polynomials and matrix exponentials. Empirical results on real-world datasets confirm that our bounds closely track the actual spectral error under diverse perturbation regimes.

Perturbation theory is developed to analyze the impact of noise on data and has been an essential part of numerical analysis. Recently, it has played an important role in designing and analyzing matrix algorithms. One of the most useful tools in this subject, the Davis-Kahan sine theorem, provides an ℓ2 error bound on the perturbation of the leading singular vectors (and spaces).

The Davis–Kahan–Wedin$\sin \Theta $theorem describes how the singular subspaces of a matrix change when subjected to a small perturbation. This classic result is sharp in the worst case scenario. In this paper, we prove a stochastic version of the Davis–Kahan–Wedin$\sin \Theta $theorem when the perturbation is a Gaussian random matrix. Under certain structural assumptions, we obtain an optimal bound that significantly improves upon the classic Davis–Kahan–Wedin$\sin \Theta $theorem. One of our key tools is a new perturbation bound for the singular values, which may be of independent interest.

The Davis–Kahan–Wedin theorem describes how the singular subspaces of a matrix change when subjected to a small perturbation. This classic result is sharp in the worst case scenario. In this paper, we prove a stochastic version of the Davis–Kahan–Wedin theorem when the perturbation is a Gaussian random matrix. Under certain structural assumptions, we obtain an optimal bound that significantly improves upon the classic Davis–Kahan–Wedin theorem. One of our key tools is a new perturbation bound for the singular values, which may be of independent interest.

A community of $n$ individuals splits into two camps, Red and Blue. The individuals are connected by a social network, which influences their colors. Everyday, each person changes his/her color according to the majority among his/her neighbors. Red (Blue) wins if everyone in the community becomes Red (Blue) at some point. We study this process when the underlying network is the random Erdos-Renyi graph $G(n, p)$. With a balanced initial state ($n/2$ person in each camp), it is clear that each color wins with the same probability. Our study reveals that for any constants $p$ and $\varepsilon$, there is a constant $C$ such that if one camp has $n/2 +C$ individuals, then it wins with probability at least $1 - \varepsilon$. The surprising key fact here is that $C$ does not depend on $n$, the population of the community. When $p=1/2$ and $\varepsilon =.1$, one can set $C$ as small as 6. If the aim of the process is to choose a candidate, then this means it takes only $6$ "defectors" to win an election unanimously with overwhelming odd.

Let A be an n x n matrix, X be an n x p matrix, and Y = AX. A challenging and important problem in data analysis, motivated by dictionary learning and other practical problems, is to recover both A and X, given Y. Under normal circumstances, it is clear that this problem is underdetermined. However, in the case, when X is sparse and random, Spielman et al. showed that one can recover both A and X efficiently from Y with high probability, given that p (the number of samples) is sufficiently large. Their method works for p ≥ Cn2log2n and they conjectured that p ≥ Cn log n suffices. The bound n log n is sharp for an obvious information theoretical reason. In this paper, we show that p ≥ Cn log4n suffices, matching the conjectural bound up to a polylogarithmic factor. The core of our proof is a theorem concerning l1concentration of random matrices, which is of independent interest. Our proof of the concentration result is based on two ideas. The first is an economical way to apply the union bound. The second is a refined version of Bernstein's concentration inequality for the sum of independent variables. Both have nothing to do with random matrices and are applicable in general settings.

In this paper, we present and analyze a simple and robust spectral algorithm for the stochastic block model with k blocks, for any k fixed. Our algorithm works with graphs having constant edge density, under an optimal condition on the gap between the density inside a block and the density between the blocks. As a co-product, we settle an open question posed by Abbe et. al. concerning censor block models.

Let X be a sparse random matrix of size n by p (p >> n). We prove that if p > C n log4 n, then with probability 1-o(1), |XT v|1 is close to its expectation for all vectors v in Rn (simultaneously). The bound on p is sharp up to the polylogarithmic factor. The study of this problem is directly motivated by an application. Let A be an n by n matrix, X be an n by p matrix and Y = AX. A challenging and important problem in data analysis, motivated by dictionary learning and other practical problems, is to recover both A and X, given Y. Under normal circumstances, it is clear that this problem is underdetermined. However, in the case when X is sparse and random, Spiel man, Wang and Wright showed that one can recover both A and X efficiently from Y with high probability, given that p (the number of samples) is sufficiently large. Their method works for p > C n2 log2 n and they conjectured that p > C n log n suffices. The bound n log n is sharp for an obvious information theoretical reason. The matrix concentration result verifies the Spiel man et. Al. Conjecture up to a log3 n factor. Our proof of the concentration result is based on two ideas. The first is an economical way to apply the union bound. The second is a refined version of Bernstein's concentration inequality for a sum of independent variables. Both have nothing to do with random matrices and are applicable in general settings.

We show that the absolute value of the determinant of a matrix with random independent (but not necessarily i.i.d.) entries is strongly concentrated around its mean. As an application, we show that Godsil–Gutman and Barvinok estimators for the permanent of a strictly positive matrix give subexponential approximation ratios with high probability. A positive answer to the main conjecture of the paper would lead to polynomial approximation ratios in the above problem.

Let M be an arbitrary n by n matrix. We study the conditionnumber a random perturbation M+Nn of M, where Nn is arandom matrix. It is shown that, under very general conditions on M and Mn, the condition number of M+Nn is polynomial in nwith very high probability. The main novelty here is that we allow Nn to have discrete distribution.

We proved several results concerning the determinant of a random pm 1 matrix. In particular, we show that with high probability, the determinant has absolute value very close to √n!.

In this paper, we present a new upper bound for the spectral norm of symmetric random matrices with independent (but not necessarily identical) entries. Our results improve an earlier result of Füredi and Komlós and also correct an incomplete argument in their proof.

Given positive integers q,n, and d, denote by A/sub q/(n,d) the maximum size of a q-ary code of length n and minimum distance d. The famous Gilbert-Varshamov bound asserts that A/sub q/(n,d+1)/spl ges/q/sup n//V/sub q/(n,d) where V/sub q/(n,d)=/spl Sigma//sub i=0//sup d/ (/sub i//sup n/)(q-1)/sup i/ is the volume of a q-ary sphere of radius d. Extending a recent work of Jiang and Vardy on binary codes, we show that for any positive constant /spl alpha/ less than (q-1)/q there is a positive constant c such that for d/spl les//spl alpha/n A/sub q/(n,d+1)/spl ges/cq/sup n//V/sub q/(n,d)n. This confirms a conjecture by Jiang and Vardy.

We show that the number of distinct distances in a well-distributed set of n points in Rd is O (n2/d-1/d2) which is not far from the best known upper bound O(n2/d).

Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple algorithm introduced by Steger and Wormald [9] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. Precisely, for fixed d and n with d=O(n1/3-e), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time O(nd2). This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality by the second author.Besides being perhaps the only algorithm which works for relatively large d in practical time, our result also has a significant theoretical value, as it can be used to derive many properties of uniform random regular graphs.

Chung and Ross [SIAM J. Comput., 20 (1991), pp. 726--736] conjectured that the minimum number m(n,r) of middle-stage switches for the symmetric 3-stage Clos network C(n,m(n,r),r) to be rearrangeable in the multirate environment is at most 2n-1. This problem is equivalent to a generalized version of the bipartite graph edge-coloring problem. The best bounds known so far on this function m(n,r) are $11n/9 \leq m(n,r) \leq 41n/16 + O(1)$, for $n, r \geq 2$, derived by Du et al. [SIAM J. Comput., 28 (1999), pp. 464--471]. In this paper, we make several contributions. First, we give evidence to show that even a stronger result might hold. In particular, we give a coloring algorithm to show that $m(n,r) \leq \lceil (r+1)n/2 \rceil$, which implies $m(n,2) \leq \lceil 3n/2 \rceil$---stronger than the conjectured value of 2n-1. Second, we derive that m(2,r) = 3 by an elegant argument. Last, we improve both the best upper and lower bounds given above: $\lceil 5n/4 \rceil \leq m(n,r) \leq 2n-1+\lceil (r-1)/2 \rceil$, where the upper bound is an improvement over $41n/16$ when r is relatively small compared to n. We also conjecture that $m(n,r) \leq \lfloor 2n(1-1/2^r) \rfloor$.

We prove a general recursive inequality concerning /spl mu//sup */(R), the asymptotic (least) density of the best binary covering codes of radius R. In particular, this inequality implies that /spl mu//sup */(R)/spl les/e/spl middot/(RlogR+logR+loglogR+2), which significantly improves the best known density 2/sup R/R/sup R/(R+1)/R!. Our inequality also holds for covering codes over arbitrary alphabets.

We prove upper and lower bounds and give an approximation algorithm for the cover time of the random walk on a graph. We introduce a parameter M motivated by the well-known Matthews bounds (P. Matthews, 1988) on the cover time, C, and prove that M/2

Studies two widely used algorithms, Glauber dynamics and the Swendsen-Wang (1987) algorithm, on rectangular subsets of the hypercubic lattice Z/sup d/. We prove that, under certain circumstances, the mixing time in a box of side length L with periodic boundary conditions can be exponential in L/sup d-1/. In other words, under these circumstances, the mixing in these widely used algorithms is not rapid; instead it is torpid. The models we study are the independent set model and the q-state Potts model. For both models, we prove that Glauber dynamics is torpid in the region with phase coexistence. For the Potts model, we prove that the Swendsen-Wang mixing is torpid at the phase transition point.

We demonstrate that the problem of training neural networks with small mean-squared error is computationally intractable. This answers a question posed by Jones (1997).

Given a set of m coins out of a collection of coins of k unknown distinct weights, the authors wish to decide if all the m given coins have the same weight or not using the minimum possible number of weighings in a regular balance beam. Let m(n,k) denote the maximum possible number of coins for which the above problem can be solved in n weighings. They show that m(n,2)=n/sup ( 1/2 +o(1))n/, whereas for all 3/spl les/k/spl les/n+1, m(n,k) is much smaller than m(n,2) and satisfies m(n,k)=/spl Theta/(n log n/log k). The proofs have an interesting geometric flavour; and combine linear algebra techniques with geometric probabilistic and combinatorial arguments.