3
views
0
recommends
+1 Recommend
0 collections
    4
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Matrix rigidity and the ill-posedness of Robust PCA and matrix completion

      Preprint
      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Robust Principal Component Analysis (PCA) (Candes et al., 2011) and low-rank matrix completion (Recht et al., 2010) are extensions of PCA to allow for outliers and missing entries respectively. It is well-known that solving these problems requires a low coherence between the low-rank matrix and the canonical basis, since in the extreme cases -- when the low-rank matrix we wish to recover is also sparse -- there is an inherent ambiguity. However, the well-posedness issue in both problems is an even more fundamental one: in some cases, both Robust PCA and matrix completion can fail to have any solutions at due to the set of low-rank plus sparse matrices not being closed, which in turn is equivalent to the notion of the matrix rigidity function not being lower semicontinuous (Kumar et al., 2014). By constructing infinite families of matrices, we derive bounds on the rank and sparsity such that the set of low-rank plus sparse matrices is not closed. We also demonstrate numerically that a wide range of non-convex algorithms for both Robust PCA and matrix completion have diverging components when applied to our constructed matrices. An analogy can be drawn to the case of sets of higher order tensors not being closed under canonical polyadic (CP) tensor rank, rendering the best low-rank tensor approximation unsolvable (Silva and Lim, 2008) and hence encourage the use of multilinear tensor rank (De Lathauwer, 2000).

          Related collections

          Most cited references30

          • Record: found
          • Abstract: not found
          • Article: not found

          Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions

            Bookmark
            • Record: found
            • Abstract: found
            • Article: found
            Is Open Access

            Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

            The affine rank minimization problem consists of finding a matrix of minimum rank that satisfies a given system of linear equality constraints. Such problems have appeared in the literature of a diverse set of fields including system identification and control, Euclidean embedding, and collaborative filtering. Although specific instances can often be solved with specialized algorithms, the general affine rank minimization problem is NP-hard. In this paper, we show that if a certain restricted isometry property holds for the linear transformation defining the constraints, the minimum rank solution can be recovered by solving a convex optimization problem, namely the minimization of the nuclear norm over the given affine space. We present several random ensembles of equations where the restricted isometry property holds with overwhelming probability. The techniques used in our analysis have strong parallels in the compressed sensing framework. We discuss how affine rank minimization generalizes this pre-existing concept and outline a dictionary relating concepts from cardinality minimization to those of rank minimization.
              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              The Power of Convex Relaxation: Near-Optimal Matrix Completion

                Bookmark

                Author and article information

                Journal
                14 November 2018
                Article
                1811.05919
                dcb81e3f-5241-4455-a3a0-563809d5b641

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                62H25, 62F35, 65F22, 65F50
                18 pages, 3 figures
                math.NA cs.IT math.IT

                Numerical & Computational mathematics,Numerical methods,Information systems & theory

                Comments

                Comment on this article