User-friendly tail bounds for sums of random matrices

DOI10.1007/S10208-011-9099-ZzbMath1259.60008DBLPjournals/focm/Tropp12arXiv1004.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 (only showing first 100 items - show all)

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

Uses Software

mftoolbox

Cites Work

This page was built for publication: User-friendly tail bounds for sums of random matrices