Smallest singular value of random matrices and geometry of random polytopes

DOI10.1016/J.AIM.2004.08.004zbMATH Open1077.15021OpenAlexW1999370902MaRDI QIDQ2484431FDOQ2484431

Authors: Alain Pajor, Alexander E. Litvak, Mark Rudelson, Nicole Tomczak-Jaegermann 

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

Recommendations

• On the smallest singular value of symmetric random matrices
• The smallest singular value of inhomogeneous square random matrices
• Random matrices: The distribution of the smallest singular values
• Lower bounds for the smallest singular value of structured random matrices
• The smallest singular value of random rectangular matrices with no moment assumptions on entries
• On the least singular value of random symmetric matrices
• An upper bound on the smallest singular value of a square random matrix
• On the singular values of random matrices
• Smallest singular value of sparse random matrices
• The smallest singular value of a shifted random matrix

zbMATH Keywords

singular valuesrandom matricesrandom polytopesdeviation inequalities

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (only showing first 100 items - show all)

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

This page was built for publication: Smallest singular value of random matrices and geometry of random polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2484431)