Exact solutions in low-rank approximation with zeros
The authors consider the problem of finding the best rank \(r\) approximation \(M'\) of a matrix \(M\), with the restriction that \(M'\) has zeroes in some fixed set of entries \(S\subset \{1,\dots,i\}\times\{1,\dots,j\}\). The solution of this structured approximation problem is not an easy consequence of results for the unstructured one, because the low rank matrices that the authors consider live in a special linear section of the corresponding secant variety. The restricted approximation problem applies to the study of non-negative approximation of matrices. The authors show how one can compute the best non-negative rank \(2\) approximation of a \(3\times 3\) matrix by considering a series of restricted approximation problems. The authors use the study of critical points for a distance function \(d_U\) in order to determine the best structured rank \(r\) approximation. For rank \(r=1\), the authors compute the number of critical points (the `Euclidean Distance degree') by a combinatorial reduction to the problem of listing minimal vertex covers of a bipartite graph. For the general case, the authors determine a bound for the dimension of the linear span of rank \(r\) critical points of \(d_U\). The authors also give a result on the unstructured approximation problem, by finding linear relations satisfied by the set of rank \(r\) critical points.
- A convex relaxation to compute the nearest structured rank deficient matrix
- A generalization of the Eckart-Young-Mirsky matrix approximation theorem
- A geometric perspective on the singular value decomposition
- A non-commutative version of Jacobi's equality on the cofactors of a matrix
- A quadratically convergent algorithm for structured low-rank approximation
- Algebraic/combinatorial proofs of Cayley-type identities for derivatives of determinants and Pfaffians
- An almost optimal algorithm for computing nonnegative rank
- An analog of the singular value decomposition for complex orthogonal equivalence
- Best rank-k approximations for tensors: generalizing Eckart-Young
- Computational Complexity
- Computing a nonnegative matrix factorization -- provably
- Exact solutions in structured low-rank approximation
- HomotopyContinuation.jl: a package for homotopy continuation in Julia
- scientific article; zbMATH DE number 108068 (Why is no real title available?)
- Lovász-Saks-Schrijver ideals and coordinate sections of determinantal varieties
- Low-rank approximation. Algorithms, implementation, applications
- Low-rank matrix approximation with weights or missing data is NP-hard
- Nonnegative matrix factorization
- Polar varieties revisited
- Structured low rank approximation
- Structured low-rank approximation and its applications
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- The distance function from a real algebraic variety
- The Euclidean distance degree of an algebraic variety
- The Euclidean distance degree of orthogonally invariant matrix varieties
- The maximum likelihood data singular locus
- The on-line encyclopedia of integer sequences
This page was built for publication: Exact solutions in low-rank approximation with zeros
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2669183)
