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

DOI10.1080/03081087.2017.1315044zbMATH Open1386.15054arXiv1406.0080OpenAlexW2963971099MaRDI QIDQ4640079FDOQ4640079

Authors: Harm Derksen 

Publication date: 16 May 2018

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

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.

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

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

zbMATH Keywords

matrix completioncomplexitytensor rankrank minimization

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Low-rank tensor completion via smooth matrix factorization
• Title not available (Why is that?)
• 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)