User-friendly tail bounds for sums of random matrices

DOI10.1007/s10208-011-9099-zzbMath1259.60008arXiv1004.4389OpenAlexW3098045837WikidataQ55967309 ScholiaQ55967309MaRDI QIDQ695625

Joel A. Tropp

Publication date: 21 December 2012

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1004.4389

zbMATH Keywords

random matrices large deviation sums of independent random variables probability inequalities discrete-time martingales

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Random matrices (probabilistic aspects) (60B20) Sums of independent random variables; random walks (60G50) Large deviations (60F10)

Related Items

Adaptive estimation of the copula correlation matrix for semiparametric elliptical copulas, The Marcinkiewicz-type discretization theorems, On the prediction loss of the Lasso in the partially labeled setting, Derandomized compressed sensing with nonuniform guarantees for $\ell_1$ recovery, Hypothesis tests for large density matrices of quantum systems based on Pauli measurements, Optimal sparse eigenspace and low-rank density matrix estimation for quantum systems, On the use of bootstrap with variational inference: theory, interpretation, and a two-sample test example, Inequalities for sums of random variables in noncommutative probability spaces, On Azuma-type inequalities for Banach space-valued martingales, Sampling discretization and related problems, Matrix completion via max-norm constrained optimization, LWE without modular reduction and improved side-channel attacks against BLISS, Sublinear time algorithms for approximate semidefinite programming, A new upper bound for sampling numbers, A rank-corrected procedure for matrix completion with fixed basis coefficients, Estimation of low rank density matrices: bounds in Schatten norms and other distances, Sharp nonasymptotic bounds on the norm of random matrices with independent entries, On tensor completion via nuclear norm minimization, Improved recovery guarantees for phase retrieval from coded diffraction patterns, Low rank matrix recovery from rank one measurements, Bayesian inference for spectral projectors of the covariance matrix, Low rank estimation of smooth kernels on graphs, A spectral algorithm with additive clustering for the recovery of overlapping communities in networks, Probably certifiably correct $k$-means clustering, Distribution of singular values of random band matrices; Marchenko-Pastur law and more, On the stability and accuracy of least squares approximations, High-dimensional covariance matrix estimation with missing observations, Spectra of edge-independent random graphs, Block Kaczmarz method with inequalities, Remote sensing via $\ell_1$-minimization, Convergence estimates in probability and in expectation for discrete least squares with noisy evaluations at random points, Finite sample behavior of a sieve profile estimator in the single index mode, Random sampling of bandlimited signals on graphs, Compressed sensing and matrix completion with constant proportion of corruptions, Sparse blind deconvolution and demixing through $\ell_{1,2}$-minimization, Adaptive multinomial matrix completion, Laguerre deconvolution with unknown matrix operator, Learning functions of few arbitrary linear parameters in high dimensions, Non-asymptotic approach to varying coefficient model, Confidence sets for spectral projectors of covariance matrices, Sparsity and incoherence in orthogonal matching pursuit, Estimating a network from multiple noisy realizations, Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality, Von Neumann entropy penalization and low-rank matrix estimation, Compressed sensing with structured sparsity and structured acquisition, Phase retrieval using random cubatures and fusion frames of positive semidefinite matrices, Finite time identification in unstable linear systems, Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion, Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression, Noncommutative martingale concentration inequalities, Sub-sampled Newton methods, Exact matrix completion based on low rank Hankel structure in the Fourier domain, Learning semidefinite regularizers, Second-order matrix concentration inequalities, Signal analysis based on complex wavelet signs, Sparse polynomial chaos expansions via compressed sensing and D-optimal design, Concentration inequalities for matrix martingales in continuous time, Stable separation and super-resolution of mixture models, Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion, Simplicial faces of the set of correlation matrices, Robust dimension-free Gram operator estimates, Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries, Random Laplacian matrices and convex relaxations, Multivariate trace inequalities, Nonparametric drift estimation for i.i.d. paths of stochastic differential equations, On polynomial time methods for exact low-rank tensor completion, Matrix factorization for multivariate time series analysis, Estimation of high-dimensional low-rank matrices, Embedded ridge approximations, Non-uniform random sampling and reconstruction in signal spaces with finite rate of innovation, Sparse space-time models: concentration inequalities and Lasso, Low-rank matrix completion in a general non-orthogonal basis, Robust group lasso: model and recoverability, Two-sample Hypothesis Testing for Inhomogeneous Random Graphs, Adaptive estimation of nonparametric geometric graphs, Distributed regularized least squares with flexible Gaussian kernels, Robust high-dimensional factor models with applications to statistical machine learning, From Poincaré inequalities to nonlinear matrix concentration, Convex optimization for the densest subgraph and densest submatrix problems, Fast community detection by SCORE, Nonlinear matrix concentration via semigroup methods, The spectra of multiplicative attribute graphs, Optimal pointwise sampling for $L^2$ approximation, $L_2$-norm sampling discretization and recovery of functions from RKHS with finite trace, The spectral norm of random lifts of matrices, Optimal selection of sample-size dependent common subsets of covariates for multi-task regression prediction, Matrix Poincaré inequalities and concentration, Error bounds of the invariant statistics in machine learning of ergodic Itô diffusions, Regression function estimation as a partly inverse problem, An elementary analysis of ridge regression with random design, On the local convergence of a stochastic semismooth Newton method for nonsmooth nonconvex optimization, A monotonicity version of a concavity theorem of Lieb, Upper and lower bounds for matrix discrepancy, Matrix concentration for products, Randomized weakly admissible meshes, Proof methods for robust low-rank matrix recovery, Information theory and recovery algorithms for data fusion in Earth observation, Relative perturbation bounds with applications to empirical covariance operators, Covariance estimation under one-bit quantization, On two continuum armed bandit problems in high dimensions, Refined analysis of sparse MIMO radar, Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction, Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames, Relaxed leverage sampling for low-rank matrix completion, On polynomial chaos expansion via gradient-enhanced $\ell_1$-minimization, Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learning, Graphs, Vectors, and Matrices, Book Review: A mathematical introduction to compressive sensing, Self-calibration and biconvex compressive sensing, Convenient tail bounds for sums of random tensors, Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods, Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time, Far-field compression for fast kernel summation methods in high dimensions, Unnamed Item, Optimal sampling and Christoffel functions on general domains, Unnamed Item, Infinite dimensional compressed sensing from anisotropic measurements and applications to inverse problems in PDE, Stable super-resolution limit and smallest singular value of restricted Fourier matrices, A randomized approach to sensor placement with observability assurance, On some extensions of Bernstein's inequality for self-adjoint operators, Spectral and matrix factorization methods for consistent community detection in multi-layer networks, The local convexity of solving systems of quadratic equations, Exponential and related probability distributions on symmetric matrices, Generalizing Lieb's concavity theorem via operator interpolation, Input perturbations for adaptive control and learning, Uniform Hanson-Wright type concentration inequalities for unbounded entries via the entropy method, A theoretical study of COmpRessed SolvING for advection-diffusion-reaction problems, Time-uniform Chernoff bounds via nonnegative supermartingales, Empirical risk minimization: probabilistic complexity and stepsize strategy, Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering, Central limit theorems for classical multidimensional scaling, Blind three dimensional deconvolution via convex optimization, Variational representations related to Tsallis relative entropy, Unnamed Item, Basis adaptive sample efficient polynomial chaos (BASE-PC), Posterior contraction in Gaussian process regression using Wasserstein approximations, Single Pass Spectral Sparsification in Dynamic Streams, Random sampling in multi-window quasi shift-invariant spaces, Stable low-rank matrix recovery via null space properties, Noncommutative Bennett and Rosenthal inequalities, A Christoffel function weighted least squares algorithm for collocation approximations, Newton-type methods for non-convex optimization under inexact Hessian information, Paved with good intentions: analysis of a randomized block Kaczmarz method, Four deviations suffice for rank 1 matrices, Noisy low-rank matrix completion with general sampling distribution, Matrix concentration inequalities via the method of exchangeable pairs, On the spectra of general random mixed graphs, Density Independent Algorithms for Sparsifying k-Step Random Walks, Finite sample performance of linear least squares estimation, ``Regression anytime with brute-force SVD truncation, Dvoretzky's theorem and the complexity of entanglement detection, Identification via Quantum Channels, An $\ell_{\infty}$ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation, Ranking and Sparsifying a Connection Graph, A generalized Lieb's theorem and its applications to spectrum estimates for a sum of random matrices, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Low-rank model with covariates for count data with missing values, Robust modifications of U-statistics and applications to covariance estimation problems, Moment inequalities for matrix-valued U-statistics of order 2, Self-Calibration and Bilinear Inverse Problems via Linear Least Squares, Spectral Compressed Sensing via Projected Gradient Descent, Relevant sampling of band-limited functions, ECA: High-Dimensional Elliptical Component Analysis in Non-Gaussian Distributions, Posterior contraction in sparse Bayesian factor models for massive covariance matrices, When do birds of a feather flock together? $k$-means, proximity, and conic programming, Optimal uniform convergence rates and asymptotic normality for series estimators under weak dependence and weak conditions, FACTORISABLE MULTITASK QUANTILE REGRESSION, Phase retrieval from coded diffraction patterns, Bernstein-type inequality for a class of dependent random matrices, Optimal weighted least-squares methods, Regression function estimation on non compact support in an heteroscesdastic model, Toward a spectral theory of cellular sheaves, Dynamic Assortment Personalization in High Dimensions, Randomized linear algebra for model reduction. I. Galerkin methods and error estimation, Model Selection via Bayesian Information Criterion for Quantile Regression Models, Concentration inequalities for random matrix products, Bootstrap confidence sets for spectral projectors of sample covariance, Structured random measurements in signal processing, Sparse Learning for Large-Scale and High-Dimensional Data: A Randomized Convex-Concave Optimization Approach, Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank, Efficient Matrix Sensing Using Rank-1 Gaussian Measurements, Low Rank Estimation of Similarities on Graphs, A parameter-free model comparison test using differential algebra, Large ball probabilities, Gaussian comparison and anti-concentration, Nonparametric estimation of low rank matrix valued function, Binary Component Decomposition Part I: The Positive-Semidefinite Case, Open and closed random walks with fixed edgelengths in $ \newcommand{\m}{\mathcal} \newcommand{\R}{\mathbb{R}} \R^d$, Preconditioning filter bank decomposition using structured normalized tight frames, Small-deviation inequalities for sums of random matrices, Consistency of spectral clustering in stochastic block models, Unnamed Item, A partial derandomization of phaselift using spherical designs, Unnamed Item, Unnamed Item, On the sample covariance matrix estimator of reduced effective rank population matrices, with applications to fPCA, Robust and computationally feasible community detection in the presence of arbitrary outlier nodes, Sparse high-dimensional varying coefficient model: nonasymptotic minimax study, Matrix Completion Methods for Causal Panel Data Models, On the Expectation of Operator Norms of Random Matrices, Convergence bounds for empirical nonlinear least-squares, Near-Optimal Sampling Strategies for Multivariate Function Approximation on General Domains, Community detection and percolation of information in a geometric setting, Near-optimal approximation methods for elliptic PDEs with lognormal coefficients, Randomized numerical linear algebra: Foundations and algorithms, Streaming Principal Component Analysis From Incomplete Data, Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits, Rigidity of Random Subgraphs and Eigenvalues of Stiffness Matrices, Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss, A comparative study of estimation methods in quantum tomography, Boosted optimal weighted least-squares, Dimension-free bounds for largest singular values of matrix Gaussian series, On expected error of randomized Nyström kernel regression, Joint Community Detection and Rotational Synchronization via Semidefinite Programming, Solving sparse principal component analysis with global support, An adaptive stochastic sequential quadratic programming with differentiable exact augmented Lagrangians, Complexity limitations on one-turn quantum refereed games, Constructive subsampling of finite frames with applications in optimal function recovery, Nearly optimal stochastic approximation for online principal subspace estimation, Optimal designs for the development of personalized treatment rules, Embracing off-the-grid samples, Nonparametric drift estimation from diffusions with correlated Brownian motions, Subsampling spectral clustering for stochastic block models in large-scale networks, Error guarantees for least squares approximation with noisy samples in domain adaptation, Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion, Pattern Formation in Random Networks Using Graphons, Probabilistic Rounding Error Analysis of Householder QR Factorization, Inference on the maximal rank of time-varying covariance matrices using high-frequency data, Universal Features for High-Dimensional Learning and Inference, Improved estimation of relaxation time in nonreversible Markov chains, Norms of structured random matrices, Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions, Multilevel weighted least squares polynomial approximation, Sparse principal component analysis for high‐dimensional stationary time series, On the reconstruction of functions from values at subsampled quadrature points, Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models, The skew spectral radius and skew Randić spectral radius of general random oriented graphs, Stochastic regularized Newton methods for nonlinear equations, APPROXIMATING SMOOTH, MULTIVARIATE FUNCTIONS ON IRREGULAR DOMAINS, Fast hyperbolic wavelet regression meets ANOVA, Hessian averaging in stochastic Newton methods achieves superlinear convergence, High-dimensional estimation of quadratic variation based on penalized realized variance, Unnamed Item, Nonparametric multiple regression by projection on non-compactly supported bases, Constructing Least-Squares Polynomial Approximations, Dimension-free bounds for sums of independent matrices and simple tensors via the variational principle, Non compact estimation of the conditional density from direct or noisy data, Covariate-Assisted Community Detection in Multi-Layer Networks, Nonparametric estimation for high-frequency data incorporating trading information, Random-reshuffled SARAH does not need full gradient computations, Determinant-Preserving Sparsification of SDDM Matrices, Unnamed Item, LSV-Based Tail Inequalities for Sums of Random Matrices, Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators, Towards optimal sampling for learning sparse approximation in high dimensions, From joint convexity of quantum relative entropy to a concavity theorem of Lieb, Spectral thresholding quantum tomography for low rank states, Scalable Algorithms for the Sparse Ridge Regression, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, The Golden-Thompson inequality: Historical aspects and random matrix applications, Unnamed Item, Integral norm discretization and related problems, On the singular value distribution of large-dimensional data matrices whose columns have different correlations, Spectral Methods for Passive Imaging: Nonasymptotic Performance and Robustness, On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization, A General Framework for Graph Sparsification, Adaptive Approximation by Optimal Weighted Least-Squares Methods, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On the Role of Total Variation in Compressed Sensing, On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems, Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds, Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization, Submatrices with NonUniformly Selected Random Supports and Insights into Sparse Approximation, Unnamed Item, Interpretable Approximation of High-Dimensional Data, Sampling complexity on phase retrieval from masked Fourier measurements via Wirtinger flow*, Fast state tomography with optimal error bounds, Nonuniform recovery of fusion frame structured sparse signals, Sequential Sampling for Optimal Weighted Least Squares Approximations in Hierarchical Spaces, Quantum Key Recycling with 8-state encoding (The Quantum One-Time Pad is more interesting than we thought), Regularization: From Inverse Problems to Large-Scale Machine Learning

Uses Software

mftoolbox

Cites Work