Note on sampling without replacing from a finite collection of matrices

Abstract

This technical note supplies an affirmative answer to a question raised in a recent pre-print [arXiv:0910.1879] in the context of a "matrix recovery" problem. Assume one samples m Hermitian matrices X_1, ..., X_m with replacement from a finite collection. The deviation of the sum X_1+...+X_m from its expected value in terms of the operator norm can be estimated by an "operator Chernoff-bound" due to Ahlswede and Winter. The question arose whether the bounds obtained this way continue to hold if the matrices are sampled without replacement. We remark that a positive answer is implied by a classical argument by Hoeffding. Some consequences for the matrix recovery problem are sketched.

3 pages. Answers a question raised in arXiv:0910.1879. v2: minus one typo.

References in corpus (3)

• Quantum state tomography via compressed sensing
• A Simpler Approach to Matrix Completion
• Robust Principal Component Analysis?

Cited by in corpus (27)

• Operational Resource Theory of Coherence
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Incoherence-Optimal Matrix Completion
• A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
• Convergence rates of sub-sampled Newton methods
• RIPless compressed sensing from anisotropic measurements
• Sub-Sampled Newton Methods II: Local Convergence Rates
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
• Optimal mini-batch and step sizes for SAGA
• Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
• Exact tensor completion using t-SVD
• Stochastic Second-order Methods for Non-convex Optimization with Inexact Hessian and Gradient
• Improved matrix algorithms via the Subsampled Randomized Hadamard Transform
• Cross: Efficient Low-rank Tensor Completion
• Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion
• The Effect of Coherence on Sampling from Matrices with Orthonormal Columns, and Preconditioned Least Squares Problems
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization
• SPAN: A Stochastic Projected Approximate Newton Method
• Low-rank Matrix Completion in a General Non-orthogonal Basis
• kappa_SQ: A Matlab package for randomized sampling of matrices with orthonormal columns
• Permutational Rademacher Complexity: a New Complexity Measure for Transductive Learning
• Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners
• On the role of total variation in compressed sensing
• Structured Matrix Completion with Applications to Genomic Data Integration
• Non-PSD Matrix Sketching with Applications to Regression and Optimization
• Graph Approximation and Clustering on a Budget