Concentration-Based Guarantees for Low-Rank Matrix Reconstruction
arXiv:1102.3923
Abstract
We consider the problem of approximately reconstructing a partially-observed, approximately low-rank matrix. This problem has received much attention lately, mostly using the trace-norm as a surrogate to the rank. Here we study low-rank matrix reconstruction using both the trace-norm, as well as the less-studied max-norm, and present reconstruction guarantees based on existing analysis on the Rademacher complexity of the unit balls of these norms. We show how these are superior in several ways to recently published guarantees based on specialized analysis.
References in corpus (1)
Cited by in corpus (18)
- Inference and Uncertainty Quantification for Noisy Matrix Completion
- Noisy low-rank matrix completion with general sampling distribution
- Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
- Enhanced Low-Rank Matrix Approximation
- Convex Tensor Decomposition via Structured Schatten Norm Regularization
- Matrix Completion via Max-Norm Constrained Optimization
- Matrix concentration inequalities via the method of exchangeable pairs
- Optimistic Rates for Learning with a Smooth Loss
- Learning tensors from partial binary measurements
- A Combinatorial Algebraic Approach for the Identifiability of Low-Rank Matrix Completion
- Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm
- Generalization error bounds for kernel matrix completion and extrapolation
- A Rank-Corrected Procedure for Matrix Completion with Fixed Basis Coefficients
- Binary Matrix Completion Using Unobserved Entries
- Calibrated Multivariate Regression with Application to Neural Semantic Basis Discovery
- Algebraic-Combinatorial Methods for Low-Rank Matrix Completion with Application to Athletic Performance Prediction
- Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion
- Online Learning with Low Rank Experts