On the equivalence between low-rank matrix completion and tensor rank

DOI10.1080/03081087.2017.1315044MaRDI QIDQ4640079zbMATH OpenOpenAlexFDO

Authors Harm Derksen

Publication date 16 May 2018

Published in Linear and Multilinear Algebra (Search for Journal in Brave)

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

zbMATH Keywords

matrix completioncomplexitytensor rankrank minimization

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Matrix completion problems (15A83)

Abstract: The Rank Minimization Problem asks to find a matrix of lowest rank inside a linear variety of the space of n x n matrices. The Low Rank Matrix Completion problem asks to complete a partially filled matrix such that the resulting matrix has smallest possible rank. The Tensor Rank Problem asks to determine the rank of a tensor. We show that these three problems are equivalent: each one of the problems can be reduced to the other two.

Recommendations

• Matrix completion and tensor rank
• Typical and generic ranks in matrix completion
• Tensor methods for nonlinear matrix completion
• Exact matrix completion via convex optimization
• On tensor completion via nuclear norm minimization

Cites work

• scientific article; zbMATH DE number 5968745 (Why is no real title available?)
• scientific article; zbMATH DE number 4158856 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• A Singular Value Thresholding Algorithm for Matrix Completion
• A comparison of algorithms for fitting the PARAFAC model
• A connection between positive semidefinite and Euclidean distance matrix completion problems
• Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
• Exact matrix completion via convex optimization
• Fixed point and Bregman iterative methods for matrix rank minimization
• General tensor decomposition, moment matrices and applications
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Index Coding With Side Information
• Interior-point method for nuclear norm approximation with application to system identification
• Matrix Completion From a Few Entries
• Matrix completion and tensor rank
• Most tensor problems are NP-hard
• Orthogonal representations over finite fields and the chromatic number of graphs
• Rank Minimization Over Finite Fields: Fundamental Limits and Coding-Theoretic Interpretations
• Rank of 3-tensors with 2 slices and Kronecker canonical forms
• Symmetric tensor decomposition
• Tensor Decompositions and Applications
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• Tensor rank is NP-complete
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• The geometry of graphs and some of its algorithmic applications

Cited in

(7)

• Low-rank tensor completion via smooth matrix factorization
• scientific article; zbMATH DE number 6474942 (Why is no real title available?)
• Low-rank tensor completion using matrix factorization based on tensor train rank and total variation
• Deterministic and Probabilistic Conditions for Finite Completability of Low-Tucker-Rank Tensor
• A non-convex tensor rank approximation for tensor completion
• Equivalence between the affine matrix rank minimization problem and the unconstrained matrix rank minimization problem
• Matrix completion and tensor rank

This page was built for publication: On the equivalence between low-rank matrix completion and tensor rank

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