Typical and generic ranks in matrix completion

DOI10.1016/J.LAA.2019.09.001MaRDI QIDQ2332456zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Irving Bernstein, Grigoriy Blekherman, Rainer Sinn

Publication date 4 November 2019

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.09513

zbMATH Keywords

generic rankmatrix completiontypical rank

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Real algebraic sets (14P05) Matrix completion problems (15A83)

Abstract: We consider the problem of exact low-rank matrix completion from a geometric viewpoint: given a partially filled matrix M, we keep the positions of specified and unspecified entries fixed, and study how the minimal completion rank depends on the values of the known entries. If the entries of the matrix are complex numbers, then for a fixed pattern of locations of specified and unspecified entries there is a unique completion rank which occurs with positive probability. We call this rank the generic completion rank. Over the real numbers there can be multiple ranks that occur with positive probability; we call them typical completion ranks. We introduce these notions formally, and provide a number of inequalities and exact results on typical and generic ranks for different families of patterns of known and unknown entries.

Recommendations

• Typical ranks in symmetric matrix completion
• A universal rank approximation method for matrix completion
• Matrix completion via minimizing an approximate rank
• Matrix completion and tensor rank
• Rank determination for low-rank data completion
• A gradual rank increasing process for matrix completion
• Maximum rank matrix completion
• Low-rank matrix completion in a general non-orthogonal basis
• Strongly stable rank and applications to matrix completion
• A rank-corrected procedure for matrix completion with fixed basis coefficients

Cites work

• A remark on global positioning from local distances
• Bipartite rigidity
• Completion of tree metrics and rank 2 matrices
• Computing images of polynomial maps
• Exact matrix completion via convex optimization
• Geometry of maximum likelihood estimation in Gaussian graphical models
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• scientific article; zbMATH DE number 5968745 (Why is no real title available?)
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 4029737 (Why is no real title available?)
• scientific article; zbMATH DE number 4107004 (Why is no real title available?)
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 5252256 (Why is no real title available?)
• Ideals, Varieties, and Algorithms
• Matrix Completion From a Few Entries
• Maximum likelihood threshold and generic completion rank of graphs
• On maximum, typical and generic ranks
• On real typical ranks
• Paths in graphs
• Perfect Elimination and Chordal Bipartite Graphs
• Rank-one completions of partial matrices and completely rank-nonincreasing linear functionals
• The algebraic combinatorial approach for low-rank matrix completion
• The geometry of rank-one tensor completion
• The lower order of lower triangular operators and minimal rank extensions
• The maximum likelihood threshold of a graph
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• The Schur complement and its applications
• Uniqueness of low-rank matrix completion by rigidity theory
• Zero forcing sets and bipartite circulants

Cited in

(21)

• Maximum rank matrix completion
• The algebraic matroid of the finite unit norm tight frame (funtf) variety
• Typical ranks in symmetric matrix completion
• Fundamental conditions on the sampling pattern for union of low-rank subspaces retrieval
• Matrix completion and tensor rank
• Uniqueness of low-rank matrix completion by rigidity theory
• Matrix completion for the independence model
• Unique low rank completability of partially filled matrices
• scientific article; zbMATH DE number 4107004 (Why is no real title available?)
• Rank determination for low-rank data completion
• On the equivalence between low-rank matrix completion and tensor rank
• Combinatorial conditions for the unique completability of low-rank matrices
• The geometry of rank-one tensor completion
• The algebraic combinatorial approach for low-rank matrix completion
• Maximum likelihood thresholds via graph rigidity
• Triangular ranks do not bound minimum ranks in matrix completion
• Entropic covariance models
• The tropical variety of symmetric rank 2 matrices
• Rank resilience of pattern matrices against structured perturbations with applications
• Multiple typical ranks in matrix completion
• Completions to discrete probability distributions in log-linear models

Describes a project that uses

Uses Software

• Macaulay2

This page was built for publication: Typical and generic ranks in matrix completion

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