Deterministic algorithms for matrix completion

DOI10.1002/RSA.20483MaRDI QIDQ2925527zbMATH OpenOpenAlexFDO

Authors Eyal Heiman, Gideon Schechtman, Adi Shraibman

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

matrix completioneigenvalueexpander graphsFrobenius normdeterministic guaranteesfactorization normsgraph sparsifiers

Mathematics Subject Classification ID

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

Recommendations

• Matrix completion from noisy entries
• Fast and near-optimal matrix completion via randomized basis pursuit
• A simpler approach to matrix completion
• Spectral regularization algorithms for learning large incomplete matrices
• Exact matrix completion via convex optimization

Cites work

• scientific article; zbMATH DE number 4032351 (Why is no real title available?)
• A simpler approach to matrix completion
• Exact matrix completion via convex optimization
• Expander graphs and their applications
• Matrix completion from noisy entries
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Ramanujan graphs
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Twice-Ramanujan sparsifiers

Cited in

(5)

• Deterministic tensor completion with hypergraph expanders
• Long time dynamics for interacting oscillators on graphs
• Spectral gap in random bipartite biregular graphs and applications
• Sparse random tensors: concentration, regularization and applications
• A divide-and-conquer algorithm for binary matrix completion

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2925527)