Deterministic algorithms for matrix completion

DOI10.1002/RSA.20483zbMATH Open1306.15027OpenAlexW2069652865MaRDI QIDQ2925527FDOQ2925527

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

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

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)

Cites Work

• Matrix completion from noisy entries
• Exact matrix completion via convex optimization
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Expander graphs and their applications
• Title not available (Why is that?)
• Ramanujan graphs
• Twice-Ramanujan sparsifiers
• A simpler approach to matrix completion

Cited In (5)

• 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
• Deterministic tensor completion with hypergraph expanders

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)