Deterministic algorithms for matrix completion

DOI10.1002/rsa.20483zbMath1306.15027OpenAlexW2069652865MaRDI QIDQ2925527

Adi Shraibman, Gideon Schechtman, Eyal Heiman

Publication date: 16 October 2014

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20483

zbMATH Keywords

eigenvaluematrix completionFrobenius normexpander graphsdeterministic guaranteesfactorization normsgraph sparsifiers

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Matrix completion problems (15A83)

Related Items (4)

Spectral gap in random bipartite biregular graphs and applications ⋮ Deterministic Tensor Completion with Hypergraph Expanders ⋮ Sparse random tensors: concentration, regularization and applications ⋮ Long time dynamics for interacting oscillators on graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Ramanujan graphs
• Exact matrix completion via convex optimization
• Expander graphs and their applications
• Twice-ramanujan sparsifiers
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• A Simpler Approach to Matrix Completion

This page was built for publication: Deterministic algorithms for matrix completion