decompy.matrix_factorization package

Submodules

decompy.matrix_factorization.adm module

class decompy.matrix_factorization.adm.AlternatingDirectionMethod(**kwargs)

Bases: object

Sparse and low-rank matrix decomposition using Alternating Direction Methods

Notes

[1] Yuan, Xiaoming, and Junfeng Yang. “Sparse and low-rank matrix decomposition via alternating direction methods.” preprint 12.2 (2009).

decompose(M: ndarray, tau: float = 0.1, beta: float | None = None, initA: ndarray | None = None, initB: ndarray | None = None, initLambda: ndarray | None = None)

Decompose a matrix M into a low-rank and sparse component using ADM.

Parameters:

  • M (ndarray) – The input matrix to decompose.

  • tau (float, optional) – Thresholding parameter. Default is 0.1.

  • beta (float or None, optional) – Regularization parameter. Default is 0.25 / abs(M).mean().

  • initA (ndarray or None, optional) – Initial guess for the sparse component. Default is zeros.

  • initB (ndarray or None, optional) – Initial guess for the low-rank component. Default is zeros.

  • initLambda (ndarray or None, optional) – Initial guess for the Lagrange multiplier. Default is zeros.

Returns:

A named tuple containing the low-rank matrix L, sparse matrix S, and convergence info.

Return type:

LSNResult

decompy.matrix_factorization.alm module

class decompy.matrix_factorization.alm.AugmentedLagrangianMethod(**kwargs)

Bases: object

Robust PCA using Augmented Lagrangian Method

Notes

[1] Gongguo Tang and A. Nehorai, “Robust principal component analysis based on low-rank and block-sparse matrix decomposition,” 2011 45th Annual Conference on Information Sciences and Systems, Baltimore, MD, USA, 2011, pp. 1-5, doi: 10.1109/CISS.2011.5766144.

decompose(M: ndarray, rank: int | None = None, kappa: float | None = None, tau: float | None = None)

Decompose a matrix M into low rank and sparse components using ALM.

Parameters:

  • M (ndarray) – Input matrix to decompose

  • rank (int, optional) – Rank of the low rank component. If not provided, will be estimated.

  • kappa (float, optional) – ALM penalty parameter. Default is 1.1 if not provided.

  • tau (float, optional) – ALM penalty parameter. Default is 0.61 if not provided.

Returns:

A named tuple containing the low rank matrix L, sparse matrix S, optional noise matrix N, and convergence info.

Return type:

LSNResult

decompy.matrix_factorization.ealm module

class decompy.matrix_factorization.ealm.ExactAugmentedLagrangianMethod(**kwargs)

Bases: object

Robust PCA using Exact Augmented Lagrangian Multiplier Method

Notes

[1] Lin, Zhouchen, Minming Chen, and Yi Ma. “The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices.” arXiv preprint arXiv:1009.5055 (2010).

decompose(M: ndarray, lambd: float | None = None, mu: float | None = None, rho: float = 6)

Decompose a matrix M into a low-rank matrix L and a sparse matrix S.

Parameters:

  • M (ndarray) – Input matrix to decompose

  • lambd (float, optional) – Weight on sparse error term in cost function. Default is 1/sqrt(m) where m is number of rows in M

  • mu (float, optional) – Regularization parameter for low-rank matrix. Default is 0.5 / norm_two where norm_two is L2 norm of M

  • rho (float, default 6) – Parameter for increasing mu at each iteration

Returns:

Named tuple containing low-rank matrix L, sparse matrix S and convergence info

Return type:

LSNResult

decompy.matrix_factorization.fpcp module

class decompy.matrix_factorization.fpcp.FastPrincipalComponentPursuit(**kwargs)

Bases: object

Robust PCA using Fast Principal Component Pursuit Method

Notes

[1] P. Rodríguez and B. Wohlberg, “Fast principal component pursuit via alternating minimization,” 2013 IEEE International Conference on Image Processing, Melbourne, VIC, Australia, 2013, pp. 69-73, doi: 10.1109/ICIP.2013.6738015.

decompose(M: ndarray, initrank: int | None = None, rank_threshold: float | None = None, lambdaval: float | None = None, lambdafactor: float | None = None)

Decompose a matrix M using FPCP method.

Parameters:

  • M (ndarray) – The input matrix to decompose.

  • initrank (int or None, optional) – The initial rank estimate. If None, set to 1. Default is None.

  • rank_threshold (float or None, optional) – The threshold value for incrementing the rank. If None, set to 0.01. Default is None.

  • lambdaval (float or None, optional) – The regularization parameter. If None, set to 1/sqrt(max(n,p)). Default is None.

  • lambdafactor (float or None, optional) – The factor to decrease lambda at each iteration. If None, set to 1. Default is None.

Returns:

A named tuple containing the final U, S, V^T matrices along with convergence information.

Return type:

SVDResult

decompy.matrix_factorization.ialm module

class decompy.matrix_factorization.ialm.InexactAugmentedLagrangianMethod(**kwargs)

Bases: object

Inexact Augmented Lagrangian Method for Robust PCA

Reference: Augmented Lagrange multiplier method for Robust PCA - Inexact method
decompose(M: ndarray, lambd: float | None = None, mu: float | None = None, rho: float = 1.5)

Decompose a matrix M into a low rank L and sparse S using Inexact ALM.

Parameters:

  • M (ndarray) – Input matrix to decompose

  • lambd (float, optional) – Weight on sparse error term in cost function. Default is 1/sqrt(m) where m is number of rows in M

  • mu (float, optional) – Initial penalty parameter. Default is 1.25 / frobenius norm of M

  • rho (float, optional) – Factor to increase mu by at each iteration. Default is 1.5

Returns:

Named tuple containing low rank L, sparse S, and convergence info.

Return type:

LSNResult

Notes

The Inexact ALM algorithm decomposes M into L and S by minimizing the objective:

||L||_* + lambd||S||_1 s.t. M = L + S

where ||.||_* is nuclear norm (sum of singular values) and ||.||_1 is L1 norm (sum of absolute values).

decompy.matrix_factorization.mest module

decompy.matrix_factorization.op module

class decompy.matrix_factorization.op.OutlierPursuit(**kwargs)

Bases: object

Matrix completion algorithm via Outlier Pursuit

Notes

[1] H. Xu, C. Caramanis and S. Sanghavi, “Robust PCA via Outlier Pursuit,” in IEEE Transactions on Information Theory, vol. 58, no. 5, pp. 3047-3064, May 2012, doi: 10.1109/TIT.2011.2173156.

decompose(M: ndarray, rank: int | None = None, lambd: float | None = None, Omega_mask: ndarray | None = None)

Decompose a matrix M into low rank matrices L and S.

Parameters:

  • M (ndarray) – The input matrix to decompose.

  • rank (int, optional) – The rank of the decomposition. If not provided, set to 10% of min(m, n).

  • lambd (float, optional) – Regularization parameter for S. If not provided, set to 1/sqrt(min(m, n)).

  • Omega_mask (ndarray, optional) – Binary mask indicating observed entries. 1 means observed. If not provided, all entries are observed.

Returns:

A named tuple containing the low rank factor L, sparse factor S and convergence information.

Return type:

LSNResult

decompy.matrix_factorization.pcp module

class decompy.matrix_factorization.pcp.PrincipalComponentPursuit(**kwargs)

Bases: object

Robust PCA using Principal Component Pursuit Method

Notes

[1] Candès, Emmanuel J., et al. “Robust principal component analysis?.” Journal of the ACM (JACM) 58.3 (2011): 1-37.

decompose(M: ndarray, lambdaval: float | None = None, muval: float | None = None)

Decompose a matrix into low-rank and sparse components using Principal Component Pursuit (PCP).

Parameters:

  • M (ndarray) – The input matrix to decompose.

  • lambdaval (float or None, optional) – Regularization parameter for the nuclear norm. Default is 1/sqrt(max(n, p)) where n, p are dimensions of M.

  • muval (float or None, optional) – Regularization parameter for the l1 norm. Default is (n*p)/(4 * abs(X).sum()) where n, p are dimensions of M.

Returns:

A named tuple containing the low-rank component U, singular values s, orthogonal matrix V and convergence metrics.

Return type:

SVDResult

decompy.matrix_factorization.rsvddpd module

class decompy.matrix_factorization.rsvddpd.RobustSVDDensityPowerDivergence(**kwargs)

Bases: object

Robust SVD using Density Power Divergence based Alternating Regression Method

Notes

[1] Roy, Subhrajyoty, Ayanendranath Basu, and Abhik Ghosh. “A New Robust Scalable Singular Value Decomposition Algorithm for Video Surveillance Background Modelling.” arXiv preprint arXiv:2109.10680 (2021).

decompose(M: ndarray, rank: int | None = None, initu: ndarray | None = None, initv: ndarray | None = None)

Decompose a matrix M into U, S, V using robust SVD.

Parameters:

  • M (ndarray) – Input matrix to decompose, of shape (n, p).

  • rank (int) – Rank of the decomposition.

  • initu (ndarray) – Left singular vectors at initialization, of shape (n, rank). Leave blank if to be initialized by initialization method.

  • initv (ndarray) – Right singular vectors at initialization, of shape (p, rank). Leave blank if to be initialized by initialization method.

Returns:

res – A tuple containing the factorization results

sigsndarray

Singular values, of shape (rank,).

Undarray

Left singular vectors, of shape (n, rank).

Vndarray

Right singular vectors, of shape (p, rank).

niterint

Number of iterations taken.

Return type:

SVDResult

Notes

Implements the rSVD-DPD algorithm from [1]_.

References

sanity_check(X: ndarray, lambdas: ndarray, maxit_reached: ndarray)

Performs sanity checks on the output.

Parameters:

  • X (ndarray) – The input data matrix

  • lambdas (ndarray) – The computed singular values

  • maxit_reached (ndarray) – Boolean array indicating if max iterations were reached

Return type:

None

Notes

Checks if max iterations were reached and warns if so. Also checks if singular values are in decreasing order.

decompy.matrix_factorization.svt module

class decompy.matrix_factorization.svt.SingularValueThresholding(**kwargs)

Bases: object

Implements the Singular Value Thresholding (SVT) algorithm for Robust PCA.

decompose(M: ndarray, lambdaval: float | None = None, tau: float | None = None, delta: float | None = None)

Decompose a matrix M into low-rank (L) and sparse (S) components.

Parameters:

  • M (ndarray) – Input matrix to decompose

  • lambdaval (float) – Regularization parameter for sparse component

  • tau (float or None, optional) – Threshold for singular values, by default None

  • delta (float or None, optional) – Step size for dual ascent, by default None

Returns:

Named tuple containing low-rank matrix L, sparse matrix S, noise matrix N, and convergence info

Return type:

LSNResult

decompy.matrix_factorization.vbrpca module

class decompy.matrix_factorization.vbrpca.VariationalBayes(**kwargs)

Bases: object

Robust PCA using Variational Bayesian method

Notes

[1] S. D. Babacan, M. Luessi, R. Molina and A. K. Katsaggelos, “Sparse Bayesian Methods for Low-Rank Matrix Estimation,” in IEEE Transactions on Signal Processing, vol. 60, no. 8, pp. 3964-3977, Aug. 2012, doi: 10.1109/TSP.2012.2197748.

decompose(M: ndarray, rank: int | None = None)

Decompose a matrix M into low rank and sparse components.

Parameters:

  • M (ndarray) – Input matrix to decompose, of shape (m, n)

  • rank (int, optional) – Rank of the low rank component. If not provided, the minimum of m and n is used.

Returns:

  • A (ndarray) – Low rank component, of shape (m, rank)

  • B (ndarray) – Low rank component, of shape (rank, n)

  • E (ndarray) – Sparse component, of shape (m, n)

  • X (ndarray) – Reconstructed low rank component A@B.T, of shape (m, n)

Module contents

class decompy.matrix_factorization.ActiveSubspaceRobustPCA(**kwargs)

Bases: object

AS-RPCA: Active Subspace: Towards Scalable Low-Rank Learning

Notes

[1] Guangcan Liu and Shuicheng Yan. 2012. Active subspace: Toward scalable low-rank learning. Neural Comput. 24, 12 (December 2012), 3371-3394. https://doi.org/10.1162/NECO_a_00369

decompose(M: ndarray, k: int | None = None, lambd=None)

Decompose a matrix into low rank and sparse components.

Decomposes the input matrix M into the sum of a low-rank matrix L and a sparse matrix S, by solving the optimization problem:

min |L|_* + lambda |S|_1 s.t. M = L + S

Parameters:

  • M (ndarray) – Input matrix to decompose

  • k (int or None, optional) – Rank of the low-rank component. If None, default is max(1, round(min(M.shape)/10))

  • lambd (float, optional) – Regularization parameter for the sparsity term. If None, default is 1/sqrt(min(M.shape))

Returns:

Named tuple containing:

L : Low-rank component

S : Sparse component

N : Null component (all zeros)

convergenceDictionary with keys:

’niter’ : Number of iterations ‘converged’ : Whether converged within max iterations ‘final_error’ : Final reconstruction error

Return type:

LSNResult

class decompy.matrix_factorization.AlternatingDirectionMethod(**kwargs)

Bases: object

Sparse and low-rank matrix decomposition using Alternating Direction Methods

Notes

[1] Yuan, Xiaoming, and Junfeng Yang. “Sparse and low-rank matrix decomposition via alternating direction methods.” preprint 12.2 (2009).

decompose(M: ndarray, tau: float = 0.1, beta: float | None = None, initA: ndarray | None = None, initB: ndarray | None = None, initLambda: ndarray | None = None)

Decompose a matrix M into a low-rank and sparse component using ADM.

Parameters:

  • M (ndarray) – The input matrix to decompose.

  • tau (float, optional) – Thresholding parameter. Default is 0.1.

  • beta (float or None, optional) – Regularization parameter. Default is 0.25 / abs(M).mean().

  • initA (ndarray or None, optional) – Initial guess for the sparse component. Default is zeros.

  • initB (ndarray or None, optional) – Initial guess for the low-rank component. Default is zeros.

  • initLambda (ndarray or None, optional) – Initial guess for the Lagrange multiplier. Default is zeros.

Returns:

A named tuple containing the low-rank matrix L, sparse matrix S, and convergence info.

Return type:

LSNResult

class decompy.matrix_factorization.AugmentedLagrangianMethod(**kwargs)

Bases: object

Robust PCA using Augmented Lagrangian Method

Notes

[1] Gongguo Tang and A. Nehorai, “Robust principal component analysis based on low-rank and block-sparse matrix decomposition,” 2011 45th Annual Conference on Information Sciences and Systems, Baltimore, MD, USA, 2011, pp. 1-5, doi: 10.1109/CISS.2011.5766144.

decompose(M: ndarray, rank: int | None = None, kappa: float | None = None, tau: float | None = None)

Decompose a matrix M into low rank and sparse components using ALM.

Parameters:

  • M (ndarray) – Input matrix to decompose

  • rank (int, optional) – Rank of the low rank component. If not provided, will be estimated.

  • kappa (float, optional) – ALM penalty parameter. Default is 1.1 if not provided.

  • tau (float, optional) – ALM penalty parameter. Default is 0.61 if not provided.

Returns:

A named tuple containing the low rank matrix L, sparse matrix S, optional noise matrix N, and convergence info.

Return type:

LSNResult

class decompy.matrix_factorization.DualRobustPCA(**kwargs)

Bases: object

This solves the robust PCA problem using dual formalization

The Primal Robust PCA relaxation

min tau ( |A|_* + lambda |E|_1 ) + 1/2 |(A,E)|_F^2 subj A+E = D

The Dual problem

max trace(D’ * Y) subj max( |Y|_2,1 + lambda |Y|_inf) <= 1

Notes

[1] Robust PCA: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization”, J. Wright et al., preprint 2009. [2] “Fast Convex Optimization Algorithms for Exact Recovery of a Corrupted Low-Rank Matrix”, Z. Lin et al., preprint 2009.

choosvd(n: int, d: int)

Choose whether to use SVD based on matrix dimensions.

Parameters:

  • n (int) – Number of rows/columns in the matrix.

  • d (int) – Rank of the matrix.

Returns:

True if SVD should be used based on the ratio of d to n, False otherwise.

Return type:

bool

decompose(M: ndarray, lambd: float | None = None)

Decompose a matrix M into two low-rank matrices using dual proximal gradient.

Parameters:

  • M (ndarray) – The input matrix to decompose.

  • lambd (float or None, optional) – Regularization parameter. Default is 1/sqrt(m) where m is the number of rows of M.

Returns:

A named tuple containing the low rank matrix L, sparse matrix S, optional noise matrix N, and convergence info.

Return type:

LSNResult

class decompy.matrix_factorization.ExactAugmentedLagrangianMethod(**kwargs)

Bases: object

Robust PCA using Exact Augmented Lagrangian Multiplier Method

Notes

[1] Lin, Zhouchen, Minming Chen, and Yi Ma. “The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices.” arXiv preprint arXiv:1009.5055 (2010).

decompose(M: ndarray, lambd: float | None = None, mu: float | None = None, rho: float = 6)

Decompose a matrix M into a low-rank matrix L and a sparse matrix S.

Parameters:

  • M (ndarray) – Input matrix to decompose

  • lambd (float, optional) – Weight on sparse error term in cost function. Default is 1/sqrt(m) where m is number of rows in M

  • mu (float, optional) – Regularization parameter for low-rank matrix. Default is 0.5 / norm_two where norm_two is L2 norm of M

  • rho (float, default 6) – Parameter for increasing mu at each iteration

Returns:

Named tuple containing low-rank matrix L, sparse matrix S and convergence info

Return type:

LSNResult

class decompy.matrix_factorization.FastPrincipalComponentPursuit(**kwargs)

Bases: object

Robust PCA using Fast Principal Component Pursuit Method

Notes

[1] P. Rodríguez and B. Wohlberg, “Fast principal component pursuit via alternating minimization,” 2013 IEEE International Conference on Image Processing, Melbourne, VIC, Australia, 2013, pp. 69-73, doi: 10.1109/ICIP.2013.6738015.

decompose(M: ndarray, initrank: int | None = None, rank_threshold: float | None = None, lambdaval: float | None = None, lambdafactor: float | None = None)

Decompose a matrix M using FPCP method.

Parameters:

  • M (ndarray) – The input matrix to decompose.

  • initrank (int or None, optional) – The initial rank estimate. If None, set to 1. Default is None.

  • rank_threshold (float or None, optional) – The threshold value for incrementing the rank. If None, set to 0.01. Default is None.

  • lambdaval (float or None, optional) – The regularization parameter. If None, set to 1/sqrt(max(n,p)). Default is None.

  • lambdafactor (float or None, optional) – The factor to decrease lambda at each iteration. If None, set to 1. Default is None.

Returns:

A named tuple containing the final U, S, V^T matrices along with convergence information.

Return type:

SVDResult

class decompy.matrix_factorization.GrassmannAverage(**kwargs)

Bases: object

GRASSMANN_AVERAGE(X) returns a basis vector for the average one-dimensional subspace spanned by the data X. This is a N-by-D matrix containing N observations in R^D.

GRASSMANN_AVERAGE(X, K) returns a D-by-K matrix of orthogonal basis vectors spanning a K-dimensional average subspace.

References

[1] “Grassmann Averages for Scalable Robust PCA”. S. Hauberg, A. Feragen and M.J. Black. In CVPR 2014. http://ps.is.tue.mpg.de/project/Robust_PCA

decompose(M: ndarray, K: int | None = None)

Decompose a matrix M into two low rank matrices using Grassmann averages.

Parameters:

  • M (ndarray) – The input matrix to decompose, of shape (N, D).

  • K (int or None, optional) – The target rank for decomposition. If not provided, default is 1.

Returns:

res – A named tuple containing the low rank factors A and B, as well as convergence diagnostics.

Return type:

RankFactorizationResult

Notes

The algorithm is based on Grassmann averages. It iteratively extracts the top K principal components while orthogonalizing them.

Examples

>>> import numpy as np
>>> from decompy.matrix_factorization import GrassmannAverage
>>> M = np.random.rand(10, 20)
>>> ga = GrassmannAverage()
>>> res = ga.decompose(M, K=5)
>>> A = res.A
>>> B = res.B
class decompy.matrix_factorization.InexactAugmentedLagrangianMethod(**kwargs)

Bases: object

Inexact Augmented Lagrangian Method for Robust PCA

Reference: Augmented Lagrange multiplier method for Robust PCA - Inexact method
decompose(M: ndarray, lambd: float | None = None, mu: float | None = None, rho: float = 1.5)

Decompose a matrix M into a low rank L and sparse S using Inexact ALM.

Parameters:

  • M (ndarray) – Input matrix to decompose

  • lambd (float, optional) – Weight on sparse error term in cost function. Default is 1/sqrt(m) where m is number of rows in M

  • mu (float, optional) – Initial penalty parameter. Default is 1.25 / frobenius norm of M

  • rho (float, optional) – Factor to increase mu by at each iteration. Default is 1.5

Returns:

Named tuple containing low rank L, sparse S, and convergence info.

Return type:

LSNResult

Notes

The Inexact ALM algorithm decomposes M into L and S by minimizing the objective:

||L||_* + lambd||S||_1 s.t. M = L + S

where ||.||_* is nuclear norm (sum of singular values) and ||.||_1 is L1 norm (sum of absolute values).

class decompy.matrix_factorization.L1Filtering(**kwargs)

Bases: object

Robust PCA using L1 Filtering

Notes

[1] Liu, R., Lin, Z., Wei, S., & Su, Z. (2011). Solving principal component pursuit in linear time via $ l_1 $ filtering. arXiv preprint arXiv:1108.5359.

decompose(M: ndarray, sr=1, sc=1)

Decompose a matrix M into low-rank, sparse and noise components using L1 factorization.

Parameters:

  • M (ndarray) – Input matrix to decompose.

  • sr (int, optional) – Number of rows to sample for initialization. Default is 1.

  • sc (int, optional) – Number of columns to sample for initialization. Default is same as sr.

Returns:

A named tuple containing the low-rank, sparse and noise components. L : ndarray

Low-rank component

Sndarray

Sparse component

Nndarray

Noise component (zeros)

convergencedict
Dictionary containing convergence info with keys:

’iteration’: number of iterations ‘converged’: boolean indicating if converged ‘error’: final error value

Return type:

LSNResult

class decompy.matrix_factorization.LinearizedADMAdaptivePenalty(**kwargs)

Bases: object

Linearized Alternating Direction Method with Adaptive Penalty

It aims to solve the LRR problem min |Z|_*+lambda*|E|_2,1 s.t., X = XZ+E, where lambda is a penalty parameter.

Notes

[1] Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation, Lin et al., 2011 - http://arxiv.org/abs/1109.0367 [2] Original MATLAB code created by Risheng Liu on 05/02/2011, rsliu0705@gmail.com

decompose(M: ndarray, rho: float | None = None, lambd: float | None = None)

Decompose a matrix M into low-rank (L), sparse (S) and noise (N) components.

Parameters:

  • M (ndarray) – The input matrix to decompose.

  • rho (float or None, optional) – The multiplicative factor to increase mu at each iteration. Default is 1.9.

  • lambd (float or None, optional) – The regularization parameter for the L1 norm of S. Default is 0.1.

Returns:

A named tuple containing the low-rank matrix L, sparse matrix S, noise matrix N and convergence details.

Return type:

LSNResult

class decompy.matrix_factorization.MixtureOfGaussianRobustPCA(**kwargs)

Bases: object

Original Author: Written by Qian Zhao (if you have any questions/comments/suggestions, please contact me: timmy.zhaoqian@gmail.com)

References

[1] “Qian Zhao, Deyu Meng, Zongben Xu, Wangmeng Zuo, Lei Zhang. Robust Principal Component Analysis with Complex Noise. ICML, 2014.”

decompose(M: ndarray, rank=None, lr_prior: LRPrior | None = None, mog_prior: MOGPrior | None = None)

Decompose a matrix M into low rank (L) and sparse noise (S) components using MOG prior.

Parameters:

  • M (ndarray) – Input matrix to decompose

  • rank (int, optional) – Rank of the low rank component. If not specified, set to min(m, n)

  • lr_prior (LRPrior, optional) – Prior for low rank component

  • mog_prior (MOGPrior, optional) – Prior for sparse noise component

Returns:

result – Result object containing: - L : Low rank component - S : Sparse noise component - N : None (not used) - convergence : Dictionary with convergence details - lr_model : Low rank model parameters - mog_model : Sparse noise model parameters

Return type:

LSNResult

class decompy.matrix_factorization.OutlierPursuit(**kwargs)

Bases: object

Matrix completion algorithm via Outlier Pursuit

Notes

[1] H. Xu, C. Caramanis and S. Sanghavi, “Robust PCA via Outlier Pursuit,” in IEEE Transactions on Information Theory, vol. 58, no. 5, pp. 3047-3064, May 2012, doi: 10.1109/TIT.2011.2173156.

decompose(M: ndarray, rank: int | None = None, lambd: float | None = None, Omega_mask: ndarray | None = None)

Decompose a matrix M into low rank matrices L and S.

Parameters:

  • M (ndarray) – The input matrix to decompose.

  • rank (int, optional) – The rank of the decomposition. If not provided, set to 10% of min(m, n).

  • lambd (float, optional) – Regularization parameter for S. If not provided, set to 1/sqrt(min(m, n)).

  • Omega_mask (ndarray, optional) – Binary mask indicating observed entries. 1 means observed. If not provided, all entries are observed.

Returns:

A named tuple containing the low rank factor L, sparse factor S and convergence information.

Return type:

LSNResult

class decompy.matrix_factorization.PrincipalComponentPursuit(**kwargs)

Bases: object

Robust PCA using Principal Component Pursuit Method

Notes

[1] Candès, Emmanuel J., et al. “Robust principal component analysis?.” Journal of the ACM (JACM) 58.3 (2011): 1-37.

decompose(M: ndarray, lambdaval: float | None = None, muval: float | None = None)

Decompose a matrix into low-rank and sparse components using Principal Component Pursuit (PCP).

Parameters:

  • M (ndarray) – The input matrix to decompose.

  • lambdaval (float or None, optional) – Regularization parameter for the nuclear norm. Default is 1/sqrt(max(n, p)) where n, p are dimensions of M.

  • muval (float or None, optional) – Regularization parameter for the l1 norm. Default is (n*p)/(4 * abs(X).sum()) where n, p are dimensions of M.

Returns:

A named tuple containing the low-rank component U, singular values s, orthogonal matrix V and convergence metrics.

Return type:

SVDResult

class decompy.matrix_factorization.RegulaizedL1AugmentedLagrangianMethod(**kwargs)

Bases: object

Implements the Regularized L1 Augmented Lagrangian algorithm for low rank matrix factorization with trace norm regularization.

Robust low-rank matrix approximation with missing data and outliers

min |W.*(M-E)|_1 + lambda*|V|_* s.t., E = UV, U’*U = I

Notes

[1] Y. Zheng, G. Liu, S. Sugimoto, S. Yan and M. Okutomi, “Practical low-rank matrix approximation under robust L1-norm,” 2012 IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, USA, 2012, pp. 1410-1417, doi: 10.1109/CVPR.2012.6247828. keywords: {Robustness;Optimization;Convergence;Computer vision;Approximation algorithms;Least squares approximation},

decompose(D: ndarray, W: ndarray | None = None, r=None, lambd: float | None = None)

Decompose a matrix D into low rank factors U and V.

Parameters:

  • D (ndarray) – The m x n data matrix to decompose.

  • W (ndarray or None, optional) – The m x n indicator matrix, with 1 representing observed entries and 0 representing missing entries. Default is None, which means all entries are observed.

  • r (int or None, optional) – The rank of the decomposition. If None, default is ceil(0.1*min(m,n)).

  • lambd (float or None, optional) – The regularization parameter. Default is 1e-3.

Returns:

res – A named tuple containing the low rank factors U and V, and convergence info such as number of iterations, error, etc.

Return type:

RankFactorizationResult

class decompy.matrix_factorization.RobustSVDDensityPowerDivergence(**kwargs)

Bases: object

Robust SVD using Density Power Divergence based Alternating Regression Method

Notes

[1] Roy, Subhrajyoty, Ayanendranath Basu, and Abhik Ghosh. “A New Robust Scalable Singular Value Decomposition Algorithm for Video Surveillance Background Modelling.” arXiv preprint arXiv:2109.10680 (2021).

decompose(M: ndarray, rank: int | None = None, initu: ndarray | None = None, initv: ndarray | None = None)

Decompose a matrix M into U, S, V using robust SVD.

Parameters:

  • M (ndarray) – Input matrix to decompose, of shape (n, p).

  • rank (int) – Rank of the decomposition.

  • initu (ndarray) – Left singular vectors at initialization, of shape (n, rank). Leave blank if to be initialized by initialization method.

  • initv (ndarray) – Right singular vectors at initialization, of shape (p, rank). Leave blank if to be initialized by initialization method.

Returns:

res – A tuple containing the factorization results

sigsndarray

Singular values, of shape (rank,).

Undarray

Left singular vectors, of shape (n, rank).

Vndarray

Right singular vectors, of shape (p, rank).

niterint

Number of iterations taken.

Return type:

SVDResult

Notes

Implements the rSVD-DPD algorithm from [1]_.

References

sanity_check(X: ndarray, lambdas: ndarray, maxit_reached: ndarray)

Performs sanity checks on the output.

Parameters:

  • X (ndarray) – The input data matrix

  • lambdas (ndarray) – The computed singular values

  • maxit_reached (ndarray) – Boolean array indicating if max iterations were reached

Return type:

None

Notes

Checks if max iterations were reached and warns if so. Also checks if singular values are in decreasing order.

class decompy.matrix_factorization.SingularValueThresholding(**kwargs)

Bases: object

Implements the Singular Value Thresholding (SVT) algorithm for Robust PCA.

decompose(M: ndarray, lambdaval: float | None = None, tau: float | None = None, delta: float | None = None)

Decompose a matrix M into low-rank (L) and sparse (S) components.

Parameters:

  • M (ndarray) – Input matrix to decompose

  • lambdaval (float) – Regularization parameter for sparse component

  • tau (float or None, optional) – Threshold for singular values, by default None

  • delta (float or None, optional) – Step size for dual ascent, by default None

Returns:

Named tuple containing low-rank matrix L, sparse matrix S, noise matrix N, and convergence info

Return type:

LSNResult

class decompy.matrix_factorization.SymmetricAlternatingDirectionALM(**kwargs)

Bases: object

This is a symmetric version of the Alternating Direction Method of Multipliers (ADMM)

Notes

[1] ‘’Fast Alternating Linearization Methods for Minimizing the Sum of Two Convex Functions’’, Donald Goldfarb, Shiqian Ma and Katya Scheinberg, Tech. Report, Columbia University, 2009 - 2010.

decompose(M: ndarray, sv: int | None = None, mu: float = 0, rho: float = 0, sigma: float = 1e-06)

Decompose a matrix M into low-rank (L), sparse (S) and noise (N) components.

Parameters:

  • M (ndarray) – The input matrix to decompose.

  • sv (int or None, optional) – The number of singular values to use in the decomposition. If None, set to 10% of min(m, n) + 1.

  • mu (float, optional) – Augmented Lagrangian parameter. Default is norm(M)/1.25.

  • rho (float, optional) – Proximal parameter for the sparse component. Default is 1/sqrt(n).

Returns:

A named tuple containing the low-rank (L), sparse (S) and noise (N) components of the decomposition, and convergence information.

Return type:

LSNResult

class decompy.matrix_factorization.VariationalBayes(**kwargs)

Bases: object

Robust PCA using Variational Bayesian method

Notes

[1] S. D. Babacan, M. Luessi, R. Molina and A. K. Katsaggelos, “Sparse Bayesian Methods for Low-Rank Matrix Estimation,” in IEEE Transactions on Signal Processing, vol. 60, no. 8, pp. 3964-3977, Aug. 2012, doi: 10.1109/TSP.2012.2197748.

decompose(M: ndarray, rank: int | None = None)

Decompose a matrix M into low rank and sparse components.

Parameters:

  • M (ndarray) – Input matrix to decompose, of shape (m, n)

  • rank (int, optional) – Rank of the low rank component. If not provided, the minimum of m and n is used.

Returns:

  • A (ndarray) – Low rank component, of shape (m, rank)

  • B (ndarray) – Low rank component, of shape (rank, n)

  • E (ndarray) – Sparse component, of shape (m, n)

  • X (ndarray) – Reconstructed low rank component A@B.T, of shape (m, n)