Riemannian CUR Decompositions for Robust Principal Component Analysis

• URL: http://arxiv.org/abs/2206.09042v1
• Date: Fri, 17 Jun 2022 22:58:09 GMT
• Title: Riemannian CUR Decompositions for Robust Principal Component Analysis
• Authors: Keaton Hamm and Mohamed Meskini and HanQin Cai
• Abstract summary: Robust Principal Component Analysis (PCA) has received massive attention in recent years. This paper proposes Robustian CUR, which is a robust PCA decomposition algorithm. It is able to tolerate a significant amount of outliers, and is comparable to Accelerated Projections, which has high outlier tolerance but worse computational complexity than the proposed method.
• Score: 4.060731229044571
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Robust Principal Component Analysis (PCA) has received massive attention in recent years. It aims to recover a low-rank matrix and a sparse matrix from their sum. This paper proposes a novel nonconvex Robust PCA algorithm, coined Riemannian CUR (RieCUR), which utilizes the ideas of Riemannian optimization and robust CUR decompositions. This algorithm has the same computational complexity as Iterated Robust CUR, which is currently state-of-the-art, but is more robust to outliers. RieCUR is also able to tolerate a significant amount of outliers, and is comparable to Accelerated Alternating Projections, which has high outlier tolerance but worse computational complexity than the proposed method. Thus, the proposed algorithm achieves state-of-the-art performance on Robust PCA both in terms of computational complexity and outlier tolerance.

Related papers

• Deep Unrolling for Nonconvex Robust Principal Component Analysis [75.32013242448151]
  We design algorithms for Robust Component Analysis (A) It consists in decomposing a matrix into the sum of a low Principaled matrix and a sparse Principaled matrix.
  arXiv  Detail & Related papers  (2023-07-12T03:48:26Z)
• Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruption [8.738540032356305]
  We develop a framework called Robust CUR for large-scale component analysis problems. We show the effectiveness and advantages of RTCUR against state methods.
  arXiv  Detail & Related papers  (2023-05-06T16:02:37Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. In this work, we present the first trial in the single-dependent generalization of AUPRC optimization. Experiments on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
  arXiv  Detail & Related papers  (2022-09-27T09:06:37Z)
• Fast Robust Tensor Principal Component Analysis via Fiber CUR Decomposition [8.821527277034336]
  We study the problem of tensor subtraction principal component analysis (TRPCA), which aims to separate an underlying low-multi-rank tensor and an outlier from their sum. In work, we propose a fast non-linear decomposition algorithm, coined Robust CURCUR, for empirically sparse problems.
  arXiv  Detail & Related papers  (2021-08-23T23:49:40Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation [48.744735294559824]
  Policy optimization methods are popular reinforcement learning algorithms, because their incremental and on-policy nature makes them more stable than the value-based counterparts. In this paper, we propose a new algorithm, COPOE, that overcomes the sample complexity issue of PCPG while retaining its robustness to model misspecification. The result is an improvement in sample complexity from $widetildeO (1/epsilon11)$ for PCPG to $widetildeO (1/epsilon3)$ for PCPG, nearly bridging the gap with value-based techniques.
  arXiv  Detail & Related papers  (2021-03-24T01:42:59Z)
• Robust CUR Decomposition: Theory and Imaging Applications [9.280330114137778]
  This paper considers the use of Robust PCA in a CUR decomposition framework and applications thereof. We consider two key imaging applications of Robust PCA: video foreground-background separation and face modeling.
  arXiv  Detail & Related papers  (2021-01-05T17:58:15Z)
• Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation [8.169365031508885]
  We propose a novel non-RPC algorithm coined Iterated Robust CUR (IRCUR) IRCUR is able to process only small submatrices and avoid expensive computing on the full matrix through the entire algorithm. Numerical experiments establish the computational advantage of IRCUR on both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2020-10-14T22:30:20Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics. Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis. We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
  arXiv  Detail & Related papers  (2020-06-23T04:25:36Z)
• On the Convergence of the Dynamic Inner PCA Algorithm [5.9931120596636935]
  DiPCA is a powerful method for the analysis of time-dependent data. We show that this is a specialized variant of a coordinate decomposition algorithm. We compare the performance of the decomposition strategies with that of the off-the-shelf It.
  arXiv  Detail & Related papers  (2020-03-12T17:50:34Z)

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.