The Algebraic Combinatorial Approach for Low-Rank Matrix Completion
We present a novel algebraic combinatorial view on low-rank matrix completion based on studying relations between a few entries with tools from algebraic geometry and matroid theory. The intrinsic locality of the approach allows for the treatment of single entries in a closed theoretical and practical framework. More specifically, apart from introducing an algebraic combinatorial theory of low-rank matrix completion, we present probability-one algorithms to decide whether a particular entry of the matrix can be completed. We also describe methods to complete that entry from a few others, and to estimate the error which is incurred by any method completing that entry. Furthermore, we show how known results on matrix completion and their sampling assumptions can be related to our new perspective and interpreted in terms of a completability phase transition.
Code (0)
등록된 구현이 없습니다.
Tasks
Low-Rank Matrix CompletionMatrix CompletionSimilar Papers 제목 키워드 기반
Algebraic-Combinatorial Methods for Low-Rank Matrix Completion with Application to Athletic Performance Prediction
This paper presents novel algorithms which exploit the intrinsic algebraic and combinatorial structure of the matrix completion task for estimating missing en- tries in the general low rank setting. For positive data, we…
Computational EfficiencyLow-Rank Matrix CompletionMatrix CompletionOpen Problem: Separating Geometric and Algorithmic Compression via Cayley-Table Completion
Modern statistical learning theory and deep learning characterize generalization primarily in terms of continuous capacity control (e.g., norm-based regularization, margin maximization, low-rank bias). While highly succe…
Algebraic Variety Models for High-Rank Matrix Completion
We consider a generalization of low-rank matrix completion to the case where the data belongs to an algebraic variety, i.e. each data point is a solution to a system of polynomial equations. In this case the original mat…
ClusteringLow-Rank Matrix CompletionMatrix CompletionVocal Bursts Intensity PredictionTensor Methods for Nonlinear Matrix Completion
In the low-rank matrix completion (LRMC) problem, the low-rank assumption means that the columns (or rows) of the matrix to be completed are points on a low-dimensional linear algebraic variety. This paper extends this t…
Low-Rank Matrix CompletionMatrix CompletionSpiky Rank and Its Applications to Rigidity and Circuits
We introduce spiky rank, a new matrix parameter that enhances blocky rank by combining the combinatorial structure of the latter with linear-algebraic flexibility. A spiky matrix is block-structured with diagonal blocks …