Lably
Skip to content

Robust principal component analysis

Method of data analysis

  • 4 min read
  • 5 chapters

Related on Lably

Through Algorithm, Computer science and Computer vision

Lab · Class 8–12Algorithms & SortingLab · Class 11Algorithm VisualizerLab · Class 11Decision Trees & Random ForestsLab · Class 10–11Reinforcement Learning Basics

Algorithms

Non-convex method

The 2014 guaranteed algorithm for the robust PCA problem (with the input matrix being M=L+S) is an alternating minimization type algorithm. The computational complexity is O(mnr2log⁡1ϵ) where the input is the superposition of a low-rank (of rank r) and a sparse matrix of dimension m×n and ϵ is the desired accuracy of the recovered solution, i.e., ‖L^−L‖F≤ϵ where L is the true low-rank component and L^ is the estimated or recovered low-rank component. Intuitively, this algorithm performs projections of the residual onto the set of low-rank matrices (via the SVD operation) and sparse matrices (via entry-wise hard thresholding) in an alternating manner - that is, low-rank projection of the difference the input matrix and the sparse matrix obtained at a given iteration followed by sparse projection of the difference of the input matrix and the low-rank matrix obtained in the previous step, and iterating the two steps until convergence.

This alternating projections algorithm is later improved by an accelerated version, coined AccAltProj. The acceleration is achieved by applying a tangent space projection before projecting the residue onto the set of low-rank matrices. This trick improves the computational complexity to O(mnrlog⁡1ϵ) with a much smaller constant in front while it maintains the theoretically guaranteed linear convergence.

Another fast version of accelerated alternating projections algorithm is IRCUR. It uses the structure of CUR decomposition in alternating projections framework to dramatically reduces the computational complexity of RPCA to O(max{m,n}r2log⁡(m)log⁡(n)log⁡1ϵ)

Convex relaxation

This method consists of relaxing the rank constraint rank(L) in the optimization problem to the nuclear norm ‖L‖∗ and the sparsity constraint ‖S‖0 to ℓ1-norm ‖S‖1. The resulting program can be solved using methods such as the method of Augmented Lagrange Multipliers.

Deep-learning augmented method

Some recent works propose RPCA algorithms with learnable/training parameters. Such a learnable/trainable algorithm can be unfolded as a deep neural network whose parameters can be learned via machine learning techniques from a given dataset or problem distribution. The learned algorithm will have superior performance on the corresponding problem distribution.

Sign in to keep reading

4 more chapters are free with a Lably account.

More in Statistics

Mortality rateDeaths per 1,000 individuals per yearSystematic reviewComprehensive review of research literature using systematic methodsSensitivity and specificityStatistical measure of a binary classificationLongitudinal studyStudy with repeated observations over timePrevalenceNumber of disease cases in a given population at a specific timeStochasticRandomly determined process