hlbotterman@quantmetry.com, jroussel@quantmetry.com, tmorzadec@quantmetry.com, rhajou@quantmetry.com, fdakhli@quantmetry.com

License: new BSD Classifier: Intended Audience :: Science/Research Classifier: Intended Audience :: Developers Classifier: License :: OSI Approved Classifier: Topic :: Software Development Classifier: Topic :: Scientific/Engineering Classifier: Operating System :: Microsoft :: Windows Classifier: Operating System :: POSIX Classifier: Operating System :: Unix Classifier: Operating System :: MacOS Classifier: Programming Language :: Python :: 3.7 Classifier: Programming Language :: Python :: 3.8 Classifier: Programming Language :: Python :: 3.9 Classifier: Programming Language :: Python :: 3.10 Requires-Python: >=3.8 Description-Content-Type: text/x-rst Provides-Extra: tests Provides-Extra: docs

RPCA for anomaly detection and data imputation

What is robust principal component analysis?

Robust Principal Component Analysis (RPCA) is a modification of the statistical procedure of principal component analysis (PCA) which allows to work with grossly corrupted observations.

Suppose we are given a large data matrix \(\mathbf{D}\), and know that it may be decomposed as

\begin{equation*} \mathbf{D} = \mathbf{X}^* + \mathbf{A}^* \end{equation*}

where \(\mathbf{X}^*\) has low-rank and \(\mathbf{A}^*\) is sparse. We do not know the low-dimensional column and row space of \(\mathbf{X}^*\), not even their dimension. Similarly, for the non-zero entries of \(\mathbf{A}^*\), we do not know their location, magnitude or even their number. Are the low-rank and sparse parts possible to recover both accurately and efficiently?

Of course, for the separation problem to make sense, the low-rank part cannot be sparse and analogously, the sparse part cannot be low-rank. See here for more details.

Formally, the problem is expressed as

\begin{equation*} \begin{align*} & \text{minimise} \quad \text{rank} (\mathbf{X}) + \lambda \Vert \mathbf{A} \Vert_0 \\ & \text{s.t.} \quad \mathbf{D} = \mathbf{X} + \mathbf{A} \end{align*} \end{equation*}

Unfortunately this optimization problem is a NP-hard problem due to its nonconvexity and discontinuity. So then, a widely used solving scheme is replacing rank(\(\mathbf{X}\)) by its convex envelope —the nuclear norm \(\Vert \mathbf{X} \Vert_*\)— and the \(\ell_0\) penalty is replaced with the \(\ell_1\)-norm, which is good at modeling the sparse noise and has high efficient solution. Therefore, the problem becomes

\begin{equation*} \begin{align*} & \text{minimise} \quad \Vert \mathbf{X} \Vert_* + \lambda \Vert \mathbf{A} \Vert_1 \\ & \text{s.t.} \quad \mathbf{D} = \mathbf{X} + \mathbf{A} \end{align*} \end{equation*}

Theoretically, this is guaranteed to work even if the rank of \(\mathbf{X}^*\) grows almost linearly in the dimension of the matrix, and the errors in \(\mathbf{A}^*\) are up to a constant fraction of all entries. Algorithmically, the above problem can be solved by efficient and scalable algorithms, at a cost not so much higher than the classical PCA. Empirically, a number of simulations and experiments suggest this works under surprisingly broad conditions for many types of real data.

Some examples of real-life applications are background modelling from video surveillance, face recognition, speech recognition. We here focus on anomaly detection in time series.

What’s in this repo?

Some classes are implemented:

RPCA class based on RPCA p.29.

GraphRPCA class based on GraphRPCA.

\begin{equation*} \begin{align*} & \text{minimise} \quad \Vert \mathbf{A} \Vert_1 + \gamma_1 \text{tr}(\mathbf{X} \mathbf{\mathcal{L}_1} \mathbf{X}^T) + \gamma_2 \text{tr}(\mathbf{X}^T \mathbf{\mathcal{L}_2} \mathbf{X}) \\ & \text{s.t.} \quad \mathbf{D} = \mathbf{X} + \mathbf{A} \end{align*} \end{equation*}

TemporalRPCA class based on Link 1 and this Link 2). The optimisation problem is the following

\begin{equation*} \text{minimise} \quad \Vert P_{\Omega}(\mathbf{X}+\mathbf{A}-\mathbf{D}) \Vert_F^2 + \lambda_1 \Vert \mathbf{X} \Vert_* + \lambda_2 \Vert \mathbf{A} \Vert_1 + \sum_{k=1}^K \eta_k \Vert \mathbf{XH_k} \Vert_p \end{equation*}

where \(\Vert \mathbf{XH_k} \Vert_p\) is either \(\Vert \mathbf{XH_k} \Vert_1\) or \(\Vert \mathbf{XH_k} \Vert_F^2\).

The operator \(P_{\Omega}\) is the projection operator such that \(P_{\Omega}(\mathbf{M})\) is the projection of \(\mathbf{M}\) on the set of observed data \(\Omega\). This allows to deal with missing values. Each of these classes is adapted to take as input either a time series or a matrix directly. If a time series is passed, a pre-processing is done.

See the examples folder for a first overview of the implemented classes.

Installation

Install directly from the gitlab repository:

Contributing

Feel free to open an issue or contact us at pnom@quantmetry.com

References

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

[2] Wang, Xuehui, et al. “An improved robust principal component analysis model for anomalies detection of subway passenger flow.” Journal of advanced transportation 2018 (2018). (pdf)

[3] Chen, Yuxin, et al. “Bridging convex and nonconvex optimization in robust PCA: Noise, outliers, and missing data.” arXiv preprint arXiv:2001.05484 (2020), (pdf)

[4] Shahid, Nauman, et al. “Fast robust PCA on graphs.” IEEE Journal of Selected Topics in Signal Processing 10.4 (2016): 740-756. (pdf)

Metadata

Release files for qolmat 0.0.5

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for qolmat 0.0.5
File	Size	Uploaded	Provenance
qolmat-0.0.5.tar.gz	16.6 kB	Mar 3, 2023	Without provenance	Details

Built distribution (wheel)

Table of built distributions (wheels) for qolmat 0.0.5
File	Interpreter	ABI	Platform	Reset
qolmat-0.0.5-py3-none-any.whl 16.4 kB Mar 3, 2023 Without provenance	Python 3	none	any	Details

Total release size: 33.0 kB

Release files / qolmat-0.0.5.tar.gz

Download URL	qolmat-0.0.5.tar.gz
Size	16.6 kB
Tags	Source
SHA-256 checksum How to use checksums	`2e710511451eb144606ad6e0810c3674f5003c0569e9d23aae8dca189f77c7a0`
BLAKE2b-256 checksum How to use checksums	`a970cb7193d9e555699ebaf0c77741023c141bf4f2c81c5a9399d40bc9429707`
Upload date	Mar 3, 2023
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/4.0.2 CPython/3.9.16`

Release files / qolmat-0.0.5-py3-none-any.whl

Download URL	qolmat-0.0.5-py3-none-any.whl
Size	16.4 kB
Tags	Python 3
SHA-256 checksum How to use checksums	`dfd47f6e130ec7d040cf0955ee6baab7b4fe23e230c722195d4e42f450ef898a`
BLAKE2b-256 checksum How to use checksums	`b70089227676667af6cc85a894504bd58e881b0115e850605397b91a807ba951`
Upload date	Mar 3, 2023
Uploaded using Trusted Publishing? What is trusted publishing?	No
Uploaded via	`twine/4.0.2 CPython/3.9.16`

Security for qolmat 0.0.5

Report project as malware

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.