Smallest singular value of random matrices and geometry of random polytopes

DOI10.1016/J.AIM.2004.08.004MaRDI QIDQ2484431zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(only showing first 100 items - show all)

• Random Euclidean embeddings in spaces of bounded volume ratio
• Singularity of discrete random matrices
• Quantitative invertibility of non-Hermitian random matrices
• A simple tool for bounding the deviation of random matrices on geometric sets
• On the robustness of minimum norm interpolators and regularized empirical risk minimizers
• 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
• Smallest singular value of a random rectangular matrix
• PROMP: a sparse recovery approach to lattice-valued signals
• Structure of eigenvectors of random regular digraphs
• From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
• Quantitative invertibility of random matrices: a combinatorial perspective
• The spectral gap of dense random regular graphs
• The strong circular law: A combinatorial view
• Singularity of sparse Bernoulli matrices
• Asymptotic shape of a random polytope in a convex body
• Sampling convex bodies: a random matrix approach
• On the hyperplane conjecture for random convex sets
• Non-negative least squares for high-dimensional linear models: consistency and sparse recovery without regularization
• The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
• Singular value decomposition of large random matrices (for two-way classification of microarrays)
• On the geometry of random polytopes
• Condition number of a square matrix with i.i.d. columns drawn from a convex body
• Estimating the probability that a given vector is in the convex hull of a random sample
• RANDOM MATRICES: THE CIRCULAR LAW
• Eigenvectors of random graphs: nodal domains
• Asymptotics for high dimensional regression \(M\)-estimates: fixed design results
• Column normalization of a random measurement matrix
• 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
• Spectrum of Markov generators on sparse random graphs
• 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
• 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
• Sketch-based multiplicative updating algorithms for symmetric nonnegative tensor factorizations with applications to face image clustering
• Row products of random matrices
• Instance-optimality in probability with an \(\ell _1\)-minimization decoder
• Polynomial bounds for large Bernoulli sections of _1N
• Small-ball probabilities for the volume of random convex sets
• Asymptotic geometric analysis: achievements and perspective
• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• Some problems in asymptotic convex geometry and random matrices motivated by numerical algorithms
• Sparse recovery from extreme eigenvalues deviation inequalities
• On delocalization of eigenvectors of random non-Hermitian matrices
• A unified framework for linear dimensionality reduction in L1
• Spectral measure of empirical autocovariance matrices of high-dimensional Gaussian stationary processes
• 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
• Invertibility of sparse non-Hermitian matrices
• Lower bounds for the smallest singular value of structured random matrices
• Smooth analysis of the condition number and the least singular value
• Poisson polyhedra in high dimensions
• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
• 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
• On the geometry of polytopes generated by heavy-tailed random vectors
• Smallest singular value and limit eigenvalue distribution of a class of non-Hermitian random matrices with statistical application
• Half-spaces with influential variable
• The smallest singular value of inhomogeneous square random matrices
• Single-pass randomized algorithms for LU decomposition
• On approximation by projections of polytopes with few facets
• An extension of a Bourgain-Lindenstrauss-Milman inequality
• Diameters of sections and coverings of convex bodies
• Circular law, extreme singular values and potential theory
• Random polytopes obtained by matrices with heavy-tailed entries
• Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries
• Randomized algorithms for the low multilinear rank approximations of tensors
• 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
• Small ball probability for the condition number of random matrices
• 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
• Randomized LU decomposition
• Stability properties of neighbourly random polytopes
• Time-based attribute-based proxy re-encryption with decryption key update
• Random polytopes generated by contoured distributions
• A theory of capacity and sparse neural encoding
• The limit of the smallest singular value of random matrices with i.i.d. entries
• Dvoretzky type theorems for subgaussian coordinate projections
• 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
• The Littlewood-Offord problem and invertibility of random matrices
• On singular values of matrices with independent rows
• Subspaces and orthogonal decompositions generated by bounded orthogonal systems
• Circular law for random matrices with unconditional log-concave distribution
• Tail bounds for gaps between eigenvalues of sparse random matrices
• Spectrum of heavy-tailed elliptic random matrices
• On the geometry of random convex sets between polytopes and zonotopes

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)