Search

Let $A \in \mathbb{R}^{N \times n}$ ($N \geq n$) be a random matrix with columns that are mean 0 and isotropic and with independent entries having bounded $2+\beta$ moments. We show that the smallest singular value $\sigma_n(A)$ satisfies \[ \Pr \left(\sigma_n(A) \leq \varepsilon(\sqrt{N+1} - \sqrt{n})\right) \leq (C\varepsilon)^{N-n+1} + e^{-cN}, \] for all $\varepsilon > 0$, where $c,C$ depend only on $\beta$ and the $2+\beta$ moments. This extends earlier results of Rudelson and Vershynin, who showed that such lower tail estimates held for rectangular matrices with i.i.d. mean-0 subgaussian entries. When the $2+\beta$ moment assumption is replaced with a uniform anti-concentration assumption, $\sup_z \Pr\left(|X-z| < a\right) < b$, we show that \[ \Pr\left(\sigma_n(A) \leq \varepsilon(\sqrt{N+1} - \sqrt{n})\right) \leq (C\varepsilon\log(1/\varepsilon))^{N-n+1} + e^{-cN}, \] where $c_2,C_3$ now depend only on $a$ and $b$. This extends more recent work of Livshyts, whose showed that such lower tail estimates held for rectrangular matrices with i.i.d. rows. To prove these results we employ a number of new technical ingredients, including a new deviation inequality for the regularized Hilbert-Schmidt norm and a recently proven small ball estimate for the distance between a random vector and a subspace spanned by an inhomogeneous rectangular matrix.

The smallest singular value and condition number play important roles in numerical linear algebra and the analysis of algorithms. In numerical analysis with randomness, many previous works make Gaussian assumptions, which are not general enough to reflect the arbitrariness of the input. To overcome this drawback, we prove the first quantitative universality for the smallest singular value and condition number of random matrices. Moreover, motivated by the study of smoothed analysis that random perturbation makes deterministic matrices well-conditioned, we consider an analog for random matrices. For a random matrix perturbed by independent Gaussian noise, we show that this matrix quickly becomes approximately Gaussian. In particular, we derive an optimal smoothed analysis for random matrices in terms of a sharp Gaussian approximation.

We derive estimates for the largest and smallest singular values of sparse rectangular $N\times n$ random matrices, assuming $\lim_{N,n\to\infty}\frac nN=y\in(0,1)$. We consider a model with sparsity parameter $p_N$ such that $Np_N\sim \log^{\alpha }N$ for some $\alpha>1$, and assume that the moments of the matrix elements satisfy the condition $\mathbf E|X_{jk}|^{4+\delta}\le C<\infty$. We assume also that the entries of matrices we consider are truncated at the level $(Np_N)^{\frac12-\varkappa}$ with $\varkappa:=\frac{\delta}{2(4+\delta)}$., Comment: arXiv admin note: text overlap with arXiv:0802.3956 by other authors

We obtain an iterative formula that converges incrementally to the smallest singular value. Similarly, we obtain an iterative formula that converges decreasingly to the largest singular value.

Let $R_n$ be a $n \times n$ random matrix with i.i.d. subgaussian entries. Let $M$ be a $n \times n$ deterministic matrix with norm $\lVert M \rVert \le n^\gamma$ where $1/2<\gamma<1$. The goal of this paper is to give a general estimate of the smallest singular value of the sum $R_n + M$, which improves an earlier result of Tao and Vu.

In this paper, we obtain two new lower bounds for the smallest singular value of nonsingular matrices which is better than the bound presented by zou \cite{zou2012lower}, Lin, Minghua and Xie, Mengyan \cite{lin2021some} under certain circumstances.

Following recent interest by the community, the scaling of the minimal singular value of a Vandermonde matrix with nodes forming clusters on the length scale of Rayleigh distance on the complex unit circle is studied. Using approximation theoretic properties of exponential sums, we show that the decay is only single exponential in the size of the largest cluster, and the bound holds for arbitrary small minimal separation distance. We also obtain a generalization of well-known bounds on the smallest eigenvalue of the generalized prolate matrix in the multi-cluster geometry. Finally, the results are extended to the entire spectrum., Comment: To appear in Applied and Computational Harmonic Analysis

Let $A$ be an $n\times n$ real matrix, and let $M$ be an $n\times n$ random matrix whose entries are i.i.d sub-Gaussian random variables with mean $0$ and variance $1$. We make two contributions to the study of $s_n(A+M)$, the smallest singular value of $A+M$. (1) We show that for all $\epsilon \geq 0$, $$\mathbb{P}[s_n(A + M) \leq \epsilon] = O(\epsilon \sqrt{n}) + 2e^{-\Omega(n)},$$ provided only that $A$ has $\Omega (n)$ singular values which are $O(\sqrt{n})$. This extends a well-known result of Rudelson and Vershynin, which requires all singular values of $A$ to be $O(\sqrt{n})$. (2) We show that any bound of the form $$\sup_{\|{A}\|\leq n^{C_1}}\mathbb{P}[s_n(A+M)\leq n^{-C_3}] \leq n^{-C_2}$$ must have $C_3 = \Omega (C_1 \sqrt{C_2})$. This complements a result of Tao and Vu, who proved such a bound with $C_3 = O(C_1C_2 + C_1 + 1)$, and counters their speculation of possibly taking $C_3 = O(C_1 + C_2)$., Comment: 15 pages; comments welcome!

Let $Q_n$ be a random $n\times n$ matrix with entries in $\{0,1\}$ whose rows are independent vectors of exactly $n/2$ zero components. We show that the smallest singular value $s_n(Q_n)$ of $Q_n$ satisfies \[ \mathbb{P}\Big\{s_n(Q_n)\le \frac{\varepsilon}{\sqrt{n}}\Big\} \le C\varepsilon + 2 e^{-cn} \quad \forall \varepsilon \ge 0, \] which is optimal up to the constants $C,c>0$. This improves on earlier results of Ferber, Jain, Luh and Samotij, as well as Jain. In particular, for $\varepsilon=0$, we obtain the first exponential bound in dimension for the singularity probability \[ \mathbb{P}\big\{Q_n \,\,\text{is singular}\big\} \le 2 e^{-cn}.\] To overcome the lack of independence between entries of $Q_n$, we introduce an arithmetic-combinatorial invariant of a pair of vectors, which we call a Combinatorial Least Common Denominator (CLCD). We prove a small ball probability inequality for the combinatorial statistic $\sum_{i=1}^{n}a_iv_{\sigma(i)}$ in terms of the CLCD of the pair $(a,v)$, where $\sigma$ is a uniformly random permutation of $\{1,2,\ldots,n\}$ and $a:=(a_1,\ldots,a_n), v:=(v_1,\ldots,v_n)$ are real vectors. This inequality allows us to derive strong anti-concentration properties for the distance between a fixed row of $Q_n$ and the linear space spanned by the remaining rows, and prove the main result., Comment: 27 pages + two appendices. Section 2.6 was rewritten. We also added an appendix by Jain, Sah and Sawhney. Update: We were recently informed that Proposition 3.4 has been proved earlier by Bero Roos [New inequalities for permanents and hafnians and some generalizations, arXiv:1906.06176v2]. As such we removed the proof of Proposition 3.4 and cited Bero Roos' paper instead

We show that for an $n\times n$ random symmetric matrix $A_n$, whose entries on and above the diagonal are independent copies of a sub-Gaussian random variable $\xi$ with mean $0$ and variance $1$, \[\mathbb{P}[s_n(A_n) \le \epsilon/\sqrt{n}] \le O_{\xi}(\epsilon^{1/8} + \exp(-\Omega_{\xi}(n^{1/2}))) \quad \text{for all } \epsilon \ge 0.\] This improves a result of Vershynin, who obtained such a bound with $n^{1/2}$ replaced by $n^{c}$ for a small constant $c$, and $1/8$ replaced by $(1/8) + \eta$ (with implicit constants also depending on $\eta > 0$). Furthermore, when $\xi$ is a Rademacher random variable, we prove that \[\mathbb{P}[s_n(A_n) \le \epsilon/\sqrt{n}] \le O(\epsilon^{1/8} + \exp(-\Omega((\log{n})^{1/4}n^{1/2}))) \quad \text{for all } \epsilon \ge 0.\] The special case $\epsilon = 0$ improves a recent result of Campos, Mattos, Morris, and Morrison, which showed that $\mathbb{P}[s_n(A_n) = 0] \le O(\exp(-\Omega(n^{1/2}))).$ The main innovation in our work are new notions of arithmetic structure -- the Median Regularized Least Common Denominator and the Median Threshold, which we believe should be more generally useful in contexts where one needs to combine anticoncentration information of different parts of a vector., Comment: 19 pages, comments welcome!

Let $n,k\geq 1$ and let $G$ be the $n\times n$ random matrix with i.i.d. standard real Gaussian entries. We show that there are constants $c_k,C_k>0$ depending only on $k$ such that the smallest singular value of $G^k$ satisfies $$ c_k\,t\leq {\mathbb P}\big\{s_{\min}(G^k)\leq t^k\,n^{-1/2}\big\}\leq C_k\,t,\quad t\in(0,1], $$ and, furthermore, $$ c_k/t\leq {\mathbb P}\big\{\|G^{-k}\|_{HS}\geq t^k\,n^{1/2}\big\}\leq C_k/t,\quad t\in[1,\infty), $$ where $\|\cdot\|_{HS}$ denotes the Hilbert-Schmidt norm., Comment: A typo corrected

Let $A$ be the adjacency matrix of a uniformly random $d$-regular digraph on $n$ vertices, and suppose that $\min(d,n-d)\geq\lambda n$. We show that for any $\kappa \geq 0$, \[\mathbb{P}[s_n(A)\leq\kappa]\leq C_\lambda\kappa\sqrt{n}+2e^{-c_\lambda n}.\] Up to the constants $C_\lambda, c_\lambda > 0$, our bound matches optimal bounds for $n\times n$ random matrices, each of whose entries is an i.i.d $\text{Ber}(d/n)$ random variable. The special case $\kappa = 0$ of our result confirms a conjecture of Cook regarding the probability of singularity of dense random regular digraphs., Comment: 21 pages; comments welcome!

We prove lower bounds for the smallest singular value of rectangular, multivariate Vandermonde matrices with nodes on the complex unit circle. The nodes are ``off the grid'', groups of nodes cluster, and the studied minimal singular value is bounded below by the product of inverted distances of a node to all other nodes in the specific cluster. By providing also upper bounds for the smallest singular value, this completely settles the univariate case and pairs of nodes in the multivariate case, both including reasonable sharp constants. For larger clusters, we show that the smallest singular value depends also on the geometric configuration within a cluster., Comment: 18 pages, 5 figures

We are concerned with the small ball behavior of the smallest singular value of random matrices. Often, establishing such results involves, in some capacity, a discretization of the unit sphere. This requires bounds on the norm of the matrix, and the latter bounds require strong assumptions on the distribution of the entries, such as bounded fourth moments (for a weak estimate), sub-gaussian tails (for a strong estimate), and structural assumptions such as mean zero and variance one. Recently, Rebrova and Tikhomirov developed a discretization procedure which does not rely on strong tail assumptions for the entries. However, their argument still required the structural assumptions of mean zero, variance one i.i.d. entries. In this paper, we discuss an efficient discretization of the unit sphere, which works with exponentially high probability, does not require any such structural assumptions, and, furthermore, does not require independence of the rows of the matrix. We show the existence of nets near the sphere, which compare values of any (deterministic) random matrix on the sphere and on the net via the regularized the Hilbert-Schmidt norm, which we introduce. Such refinement is a form of averaging, and enjoys strong large deviation properties. As a consequence we show sharp small ball estimates for the smallest singular value of square random matrices under mild assumptions, and for the random matrices with arbitrary aspect ratio., Comment: 38 pages. One out of N-n+2 logarithms removed. Some comments and remarks added

We show that for an $n\times n$ random matrix $A$ with independent uniformly anti-concentrated entries, such that $\mathbb{E} ||A||^2_{HS}\leq K n^2$, the smallest singular value $\sigma_n(A)$ of $A$ satisfies $$ P\left( \sigma_n(A)\leq \frac{\varepsilon}{\sqrt{n}} \right) \leq C\varepsilon+2e^{-cn},\quad \varepsilon \ge 0. $$ This extends earlier results of Rudelson and Vershynin, and Rebrova and Tikhomirov by removing the assumption of mean zero and identical distribution of the entries across the matrix, as well as the recent result of Livshyts, where the matrix was required to have i.i.d. rows. Our model covers "inhomogeneus" matrices allowing different variances of the entries, as long as the sum of the second moments is of order $O(n^2)$. In the past advances, the assumption of i.i.d. rows was required due to lack of Littlewood--Offord--type inequalities for weighted sums of non-i.i.d. random variables. Here, we overcome this problem by introducing the Randomized Least Common Denominator (RLCD) which allows to study anti-concentration properties of weighted sums of independent but not identically distributed variables. We construct efficient nets on the sphere with lattice structure, and show that the lattice points typically have large RLCD. This allows us to derive strong anti-concentration properties for the distance between a fixed column of $A$ and the linear span of the remaining columns, and prove the main result., Comment: 24 pages, final version

Suppose $X$ is an $N \times n$ complex matrix whose entries are centered, independent, and identically distributed random variables with variance $1/n$ and whose fourth moment is of order ${\mathcal O}(n^{-2})$. In the first part of the paper, we consider the non-Hermitian matrix $X A X^* - z$, where $A$ is a deterministic matrix whose smallest and largest singular values are bounded below and above respectively, and $z\neq 0$ is a complex number. Asymptotic probability bounds for the smallest singular value of this model are obtained in the large dimensional regime where $N$ and $n$ diverge to infinity at the same rate. In the second part of the paper, we consider the special case where $A = J = [1_{i-j = 1\mod n} ]$ is a circulant matrix. Using the result of the first part, it is shown that the limit eigenvalue distribution of $X J X^*$ exists in the large dimensional regime, and we determine this limit explicitly. A statistical application of this result devoted towards testing the presence of correlations within a multivariate time series is considered. Assuming that $X$ represents a ${\mathbb C}^N$-valued time series which is observed over a time window of length $n$, the matrix $X J X^*$ represents the one-step sample autocovariance matrix of this time series. Guided by the result on the limit spectral measure of this matrix, a whiteness test against an MA correlation model on the time series is introduced. Numerical simulations show the excellent performance of this test., Comment: 43 pages, 6 figures

Let $A = (a_{ij})$ be a square $n\times n$ matrix with i.i.d. zero mean and unit variance entries. Rudelson and Vershynin showed that the upper bound for a smallest singular value $s_n(A)$ is of order $n^{-\frac12}$ with probability close to one under additional assumption on entries of $A$ that $\mathbb{E}a^4_{11} < \infty$. We remove the assumption on the fourth moment and show the upper bound assuming only $\mathbb{E}a^2_{11} = 1.$, Comment: 14 pages; A few typos corrected

We derive a lower bound on the smallest singular value of a random $d$-regular matrix, that is, the adjacency matrix of a random $d$-regular directed graph. More precisely, let $C_1

We prove an estimate on the smallest singular value of a multiplicatively and additively deformed random rectangular matrix. Suppose $n\le N \le M \le \Lambda N$ for some constant $\Lambda \ge 1$. Let $X$ be an $M\times n$ random matrix with independent and identically distributed entries, which have zero mean, unit variance and arbitrarily high moments. Let $T$ be an $N\times M$ deterministic matrix with comparable singular values $c\le s_{N}(T) \le s_{1}(T) \le c^{-1}$ for some constant $c>0$. Let $A$ be an $N\times n$ deterministic matrix with $\|A\|=O(\sqrt{N})$. Then we prove that for any $\epsilon>0$, the smallest singular value of $TX-A$ is larger than $N^{-\epsilon}(\sqrt{N}-\sqrt{n-1})$ with high probability. If we assume further the entries of $X$ have subgaussian decay, then the smallest singular value of $TX-A$ is at least of the order $\sqrt{N}-\sqrt{n-1}$ with high probability, which is an essentially optimal estimate., Comment: 23 pages

We consider the inverse problem of recovering the locations and amplitudes of a collection of point sources represented as a discrete measure, given $M+1$ of its noisy low-frequency Fourier coefficients. Super-resolution refers to a stable recovery when the distance $\Delta$ between the two closest point sources is less than $1/M$. We introduce a clumps model where the point sources are closely spaced within several clumps. Under this assumption, we derive a non-asymptotic lower bound for the minimum singular value of a Vandermonde matrix whose nodes are determined by the point sources. Our estimate is given as a weighted $\ell^2$ sum, where each term only depends on the configuration of each individual clump. The main novelty is that our lower bound obtains an exact dependence on the {\it Super-Resolution Factor} $SRF=(M\Delta)^{-1}$. As noise level increases, the {\it sensitivity of the noise-space correlation function in the MUSIC algorithm} degrades according to a power law in $SRF$ where the exponent depends on the cardinality of the largest clump. Numerical experiments validate our theoretical bounds for the minimum singular value and the sensitivity of MUSIC. We also provide lower and upper bounds for a min-max error of super-resolution for the grid model, which in turn is closely related to the minimum singular value of Vandermonde matrices., Comment: fixed some typos; 40 pages, 5 figures; Applied and Computational Harmonic Analysis 2021

We obtain lower tail estimates for the smallest singular value of random matrices with independent but non-identically distributed entries. Specifically, we consider $n\times n$ matrices with complex entries of the form \[ M = A\circ X + B = (a_{ij}\xi_{ij} + b_{ij}) \] where $X=(\xi_{ij})$ has iid centered entries of unit variance and $A$ and $B$ are fixed matrices. In our main result we obtain polynomial bounds on the smallest singular value of $M$ for the case that $A$ has bounded (possibly zero) entries, and $B= Z\sqrt{n}$ where $Z$ is a diagonal matrix with entries bounded away from zero. As a byproduct of our methods we can also handle general perturbations $B$ under additional hypotheses on $A$, which translate to connectivity hypotheses on an associated graph. In particular, we extend a result of Rudelson and Zeitouni for Gaussian matrices to allow for general entry distributions satisfying some moment hypotheses. Our proofs make use of tools which (to our knowledge) were previously unexploited in random matrix theory, in particular Szemer\'edi's Regularity Lemma, and a version of the Restricted Invertibility Theorem due to Spielman and Srivastava., Comment: 69 pages. To appear in Annals of Probability

Let $F(x) := (f_{ij}(x))_{i=1,\ldots,p; j=1,\ldots,q},$ be a ($p\times q$)-real polynomial matrix and let $f(x)$ be the smallest singular value function of $F(x).$ In this paper, we first give the following {\em nonsmooth} version of \L ojasiewicz gradient inequality for the function $f$ with an explicit exponent: {\em For any $\bar x\in \Bbb R^n$, there exist $c > 0$ and $\epsilon > 0$ such that we have for all $\|x - \bar{x}\| < \epsilon,$ \begin{equation*} \inf \{ \| w \| \ : \ w \in {\partial} f(x) \} \ \ge \ c\, |f(x)-f(\bar x)|^{1 - \frac{2}{\mathscr R(n+p,2d+2)}}, \end{equation*} where ${\partial} f(x)$ is the limiting subdifferential of $f$ at $x$, $d:=\max_{i=1,\ldots,p; j=1,\ldots,q}\deg f_{i j}$ and $\mathscr R(n, d) := d(3d - 3)^{n-1}$ if $d \ge 2$ and $\mathscr R(n, d) := 1$ if $d = 1.$} Then we establish some versions of \L ojasiewicz inequality for the distance function with explicit exponents, locally and globally, for the smallest singular value function $f(x)$ of the matrix $F(x)$.

Let $\{a_{ij}\}$ $(1\le i,j<\infty)$ be i.i.d. real valued random variables with zero mean and unit variance and let an integer sequence $(N_m)_{m=1}^\infty$ satisfy $m/N_m\longrightarrow z$ for some $z\in(0,1)$. For each $m\in{\mathbb N}$ denote by $A_m$ the $N_m\times m$ random matrix $(a_{ij})$ $(1\le i\le N_m,1\le j\le m)$ and let $s_{m}(A_m)$ be its smallest singular value. We prove that the sequence $\bigl({N_m}^{-1/2} s_{m}(A_m)\bigr)_{m=1}^\infty$ converges to $1-\sqrt{z}$ almost surely. Our result does not require boundedness of any moments of $a_{ij}$'s higher than the $2$-nd and resolves a long standing question regarding the weakest moment assumptions on the distribution of the entries sufficient for the convergence to hold.

Let $\delta>1$ and $\beta>0$ be some real numbers. We prove that there are positive $u,v,N_0$ depending only on $\beta$ and $\delta$ with the following property: for any $N,n$ such that $N\ge \max(N_0,\delta n)$, any $N\times n$ random matrix $A=(a_{ij})$ with i.i.d. entries satisfying $\sup\limits_{\lambda\in {\mathbb R}}{\mathbb P}\bigl\{|a_{11}-\lambda|\le 1\bigr\}\le 1-\beta$ and any non-random $N\times n$ matrix $B$, the smallest singular value $s_n$ of $A+B$ satisfies ${\mathbb P}\bigl\{s_n(A+B)\le u\sqrt{N}\bigr\}\le \exp(-vN)$. The result holds without any moment assumptions on distribution of the entries of $A$.

We take a first small step to extend the validity of Rudelson-Vershynin type estimates to some sparse random matrices, here random permutation matrices. We give lower (and upper) bounds on the smallest singular value of a large random matrix D+M where M is a random permutation matrix, sampled uniformly, and D is diagonal. When D is itself random with i.i.d terms on the diagonal, we obtain a Rudelson-Vershynin type estimate, using the classical theory of random walks with negative drift., Comment: 33 pages

Given $X$ a random vector in ${\mathbb{R}}^n$, set $X_1,...,X_N$ to be independent copies of $X$ and let $\Gamma=\frac{1}{\sqrt{N}}\sum_{i=1}^N e_i$ be the matrix whose rows are $\frac{X_1}{\sqrt{N}},\dots, \frac{X_N}{\sqrt{N}}$. We obtain sharp probabilistic lower bounds on the smallest singular value $\lambda_{\min}(\Gamma)$ in a rather general situation, and in particular, under the assumption that $X$ is an isotropic random vector for which $\sup_{t\in S^{n-1}}{\mathbb{E}}||^{2+\eta} \leq L$ for some $L,\eta>0$. Our results imply that a Bai-Yin type lower bound holds for $\eta>2$, and, up to a log-factor, for $\eta=2$ as well. The bounds hold without any additional assumptions on the Euclidean norm $\|X\|_{\ell_2^n}$. Moreover, we establish a nontrivial lower bound even without any higher moment assumptions (corresponding to the case $\eta=0$), if the linear forms satisfy a weak `small ball' property.

We prove an optimal estimate on the smallest singular value of a random subgaussian matrix, valid for all fixed dimensions. For an N by n matrix A with independent and identically distributed subgaussian entries, the smallest singular value of A is at least of the order \sqrt{N} - \sqrt{n-1} with high probability. A sharp estimate on the probability is also obtained., Comment: 33 pages. A few misprints corrected