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

deviation inequalitiesrandom matricesrandom polytopessingular values

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Inequalities involving eigenvalues and eigenvectors (15A42) Miscellaneous inequalities involving matrices (15A45) Random matrices (algebraic aspects) (15B52) 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

• 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
• 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?)
• 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 best constants in the Khintchine inequality
• The concentration of measure phenomenon
• The Distribution of Rademacher Sums
• 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)

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

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)