Unique sparse decomposition of low rank matrices

• URL: http://arxiv.org/abs/2106.07736v1
• Date: Mon, 14 Jun 2021 20:05:59 GMT
• Title: Unique sparse decomposition of low rank matrices
• Authors: Dian Jin, Xin Bing and Yuqian Zhang
• Abstract summary: We find a unique decomposition of a low rank matrixYin mathbbRrtimes n$. We prove that up to some $Yin mathRrtimes n$ is a sparse-wise decomposition of $Xin mathbbRrtimes n$.
• Score: 17.037882881652617
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of finding the unique low dimensional decomposition of a given matrix has been a fundamental and recurrent problem in many areas. In this paper, we study the problem of seeking a unique decomposition of a low rank matrix $Y\in \mathbb{R}^{p\times n}$ that admits a sparse representation. Specifically, we consider $Y = A X\in \mathbb{R}^{p\times n}$ where the matrix $A\in \mathbb{R}^{p\times r}$ has full column rank, with $r < \min\{n,p\}$, and the matrix $X\in \mathbb{R}^{r\times n}$ is element-wise sparse. We prove that this sparse decomposition of $Y$ can be uniquely identified, up to some intrinsic signed permutation. Our approach relies on solving a nonconvex optimization problem constrained over the unit sphere. Our geometric analysis for the nonconvex optimization landscape shows that any {\em strict} local solution is close to the ground truth solution, and can be recovered by a simple data-driven initialization followed with any second order descent algorithm. At last, we corroborate these theoretical results with numerical experiments.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  We propose a natural algorithm that involves imputing the missing values of the matrix $XTX$. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing.
  arXiv  Detail & Related papers  (2023-06-06T22:35:16Z)
• A General Algorithm for Solving Rank-one Matrix Sensing [15.543065204102714]
  The goal of matrix sensing is to recover a matrix $A_star in mathbbRn times n$, based on a sequence of measurements. In this paper, we relax that rank-$k$ assumption and solve a much more general matrix sensing problem.
  arXiv  Detail & Related papers  (2023-03-22T04:07:26Z)
• Low-rank Matrix Recovery With Unknown Correspondence [62.634051913953485]
  We show that it is possible to recover $M$ via solving a nuclear norm minimization problem under a proper low-rank condition on $M$, with provable non-asymptotic error bound for the recovery of $M$. Experiments on simulated data, the MovieLens 100K dataset and Yale B database show that $textM3textO achieves state-of-the-art performance over several baselines and can recover the ground-truth correspondence with high accuracy.
  arXiv  Detail & Related papers  (2021-10-15T09:27:50Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
  We study the asymmetric low-rank factorization problem: [mathbfU in mathbbRm min d, mathbfU$ and mathV$.
  arXiv  Detail & Related papers  (2021-06-27T17:25:24Z)
• Local Search Algorithms for Rank-Constrained Convex Optimization [7.736462653684946]
  We propose greedy and local search algorithms for rank-constrained convex optimization. We show that if the rank-restricted condition number of $R$ is $kappa$, a solution $A$ with rank $O(r*cdot minkappa log fracR(mathbf0)-R(A*)epsilon, kappa2)$ and $R(A) leq R(A*) + epsilon$ can be recovered, where $A
  arXiv  Detail & Related papers  (2021-01-15T18:52:02Z)
• Compressed sensing of low-rank plus sparse matrices [3.8073142980733]
  This manuscript develops similar guarantees showing that $mtimes n$ that can be expressed as the sum of a rank-rparse matrix and a $s-sparse matrix can be recovered by computationally tractable methods. Results are shown for synthetic problems, dynamic-foreground/static separation, multispectral imaging, and Robust PCA.
  arXiv  Detail & Related papers  (2020-07-18T15:36:11Z)
• Optimal Exact Matrix Completion Under new Parametrization [0.0]
  We study the problem of exact completion for $m times n$ sized matrix of rank $r$ with the adaptive sampling method. We propose matrix completion algorithms that exactly recovers the target matrix.
  arXiv  Detail & Related papers  (2020-02-06T18:31:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.