Smallest singular value of random matrices and geometry of random polytopes

DOI10.1016/j.aim.2004.08.004zbMath1077.15021OpenAlexW1999370902MaRDI QIDQ2484431

Alain Pajor, M. V. Rudel'son, Nicole Tomczak-Jaegermann, Alexander E. Litvak

Publication date: 1 August 2005

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aim.2004.08.004

zbMATH Keywords

random matricessingular valuesrandom polytopesdeviation inequalities

Mathematics Subject Classification ID

Inequalities involving eigenvalues and eigenvectors (15A42) Random operators and equations (aspects of stochastic analysis) (60H25) Eigenvalues, singular values, and eigenvectors (15A18) Miscellaneous inequalities involving matrices (15A45) Random matrices (algebraic aspects) (15B52)

Related Items

Spectral measure of empirical autocovariance matrices of high-dimensional Gaussian stationary processes, Condition number of a square matrix with i.i.d. columns drawn from a convex body, Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries, Random Euclidean embeddings in spaces of bounded volume ratio, Singularity of discrete random matrices, Smooth analysis of the condition number and the least singular value, Lower bounds for the smallest singular value of structured random matrices, Singularity of sparse Bernoulli matrices, Asymptotics for high dimensional regression \(M\)-estimates: fixed design results, Diameters of sections and coverings of convex bodies, Random sections of ellipsoids and the power of random information, Berry-Esseen bounds and multivariate limit theorems for functionals of Rademacher sequences, On the hyperplane conjecture for random convex sets, LWE without modular reduction and improved side-channel attacks against BLISS, The smallest singular value of random rectangular matrices with no moment assumptions on entries, The method of perpendiculars of finding estimates from below for minimal singular eigenvalues of random matrices, A unified framework for linear dimensionality reduction in L1, Circular law, extreme singular values and potential theory, On the decay of the smallest singular value of submatrices of rectangular matrices, On the geometry of polytopes generated by heavy-tailed random vectors, From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices, PROMP: a sparse recovery approach to lattice-valued signals, Erratum to: Outliers in the spectrum of iid matrices with bounded rank perturbations, On singular values of matrices with independent rows, Smallest singular value and limit eigenvalue distribution of a class of non-Hermitian random matrices with statistical application, On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence, Subspaces and orthogonal decompositions generated by bounded orthogonal systems, On delocalization of eigenvectors of random non-Hermitian matrices, Non-negative least squares for high-dimensional linear models: consistency and sparse recovery without regularization, Concentration and universal randomisation of proper subspaces, Quantitative invertibility of random matrices: a combinatorial perspective, A theory of capacity and sparse neural encoding, Randomized LU decomposition, Half-Spaces with Influential Variable, On the largest and the smallest singular value of sparse rectangular random matrices, Quantitative invertibility of non-Hermitian random matrices, The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection, Random polytopes obtained by matrices with heavy-tailed entries, Estimating the probability that a given vector is in the convex hull of a random sample, Small Ball Probability for the Condition Number of Random Matrices, On the Geometry of Random Polytopes, Around the circular law, Random embedding of \({\ell_p^n}\) into \({\ell_r^N}\), RANDOM MATRICES: THE CIRCULAR LAW, Quermaßintegrals and asymptotic shape of random polytopes in an isotropic convex body, On the isotropy constant of random convex sets, Direct computation of branching programs and its applications to more efficient lattice-based cryptography, Mean width of random perturbations of random polytopes, Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries, Small-ball probabilities for the volume of random convex sets, Kahane-Khinchin type averages, Structure of eigenvectors of random regular digraphs, On approximation by projections of polytopes with few facets, Randomized algorithms for the low multilinear rank approximations of tensors, The spectral gap of dense random regular graphs, Poincaré inequality in mean value for Gaussian polytopes, An extension of a Bourgain-Lindenstrauss-Milman inequality, Smallest singular value of random matrices with independent columns, The smallest singular value of a shifted $d$-regular random square matrix, The limit of the smallest singular value of random matrices with i.i.d. entries, Dvoretzky type theorems for subgaussian coordinate projections, On the geometry of random convex sets between polytopes and zonotopes, Column normalization of a random measurement matrix, Polynomial bounds for large Bernoulli sections of \(\ell_1^N\), Invertibility of sparse non-Hermitian matrices, Random matrices: tail bounds for gaps between eigenvalues, Spectrum of Markov Generators on Sparse Random Graphs, Row products of random matrices, The Littlewood-Offord problem and invertibility of random matrices, A Large Deviations Approach to the Geometry of Random Polytopes, Stability and instance optimality for Gaussian measurements in compressed sensing, Random matrices: The distribution of the smallest singular values, Spectral norm of products of random and deterministic matrices, The circular law for random matrices, An upper bound on the smallest singular value of a square random matrix, Eigenvectors of random graphs: Nodal Domains, Sharp transition of the invertibility of the adjacency matrices of sparse random graphs, No-gaps delocalization for general random matrices, Instance-optimality in probability with an \(\ell _1\)-minimization decoder, Asymptotic shape of a random polytope in a convex body, The smallest singular value of inhomogeneous square random matrices, Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices, An efficient randomized algorithm for computing the approximate Tucker decomposition, Stability properties of neighbourly random polytopes, Single-pass randomized algorithms for LU decomposition, Sparse recovery from extreme eigenvalues deviation inequalities, Smallest singular value of a random rectangular matrix, The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding, Tail bounds for gaps between eigenvalues of sparse random matrices, Spectrum of heavy-tailed elliptic random matrices, Random matrix products: universality and least singular values, Singular value decomposition of large random matrices (for two-way classification of microarrays), On the robustness of minimum norm interpolators and regularized empirical risk minimizers, Sampling convex bodies: a random matrix approach, Large-deviation asymptotics of condition numbers of random matrices, On some aspects of approximation of ridge functions, The strong circular law: A combinatorial view, Circular law for random matrices with unconditional log-concave distribution, Poisson polyhedra in high dimensions, Lower estimates for the singular values of random matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
• The finite dimensional basis problem with an appendix on nets of Grassmann manifolds
• The smallest eigenvalue of a large dimensional Wishart matrix
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• Some inequalities for Gaussian processes and applications
• Gelfand numbers of operators with values in a Hilbert space
• Diameter of the Minkowski compactum is approximately equal to n
• New volume ratio properties for convex symmetric bodies in \({\mathbb{R}}^ n\)
• Random spaces generated by vertices of the cube
• Random Euclidean embeddings in spaces of bounded volume ratio
• The Distribution of Rademacher Sums
• Approximation of the Sphere by Polytopes having Few Vertices
• Eigenvalues and Condition Numbers of Random Matrices
• The best constants in the Khintchine inequality
• Volumes Spanned by Random Points in the Hypercube
• Deterministic and randomized polynomial‐time approximation of radii
• On the Probability That a Random ± 1-Matrix Is Singular
• Probability Inequalities for Sums of Bounded Random Variables
• John's decompositions: Selecting a large part
• On 0-1 polytopes with many facets