Robust PCA

RPCA solves the fundamental decomposition problem X = L + S, where L is a low-rank matrix representing the intrinsic structure of normal transactions and S is a sparse matrix capturing outliers. Unlike classical PCA, which is highly sensitive to even a single corrupted observation, RPCA leverages Principal Component Pursuit (PCP) to exactly recover both components under broad conditions. The optimization minimizes the nuclear norm of L (promoting low rank) and the L1 norm of S (promoting sparsity), solved via Augmented Lagrange Multiplier (ALM) methods. This separation allows fraud analysts to inspect the sparse matrix S directly for anomalous transaction patterns.

Classical PCA fails catastrophically when even a small fraction of data points are corrupted because the L2-norm minimization squares errors, giving disproportionate influence to outliers. RPCA replaces this with an L1-norm penalty on the sparse component, making it provably robust to gross corruptions affecting up to a constant fraction of entries. Key properties include:

• Breakdown point: Tolerates corruption levels proportional to the inverse of the matrix rank
• No prior outlier labeling: Operates in a fully unsupervised manner
• Entry-wise and row-wise corruption: Handles both random scattered anomalies and entire corrupted rows (e.g., compromised merchant terminals) This robustness is critical in financial fraud where adversarial actors deliberately inject anomalous patterns designed to evade detection.

The workhorse algorithm for solving RPCA is the Inexact Augmented Lagrange Multiplier (IALM) method, which offers superior convergence speed compared to Accelerated Proximal Gradient or Singular Value Thresholding alternatives. The algorithm:

• Alternately updates L, S, and the Lagrange multiplier Y
• Uses soft-thresholding on singular values to enforce the nuclear norm constraint
• Applies shrinkage operators to enforce sparsity on S
• Converges in O(1/k²) iterations under standard conditions In practice, IALM can decompose a 10,000 × 10,000 transaction matrix in seconds on modern hardware, making it viable for daily batch fraud screening pipelines. The exact ALM variant guarantees convergence but at higher per-iteration cost.

Once decomposition is complete, the sparse matrix S serves as a direct anomaly indicator. Each entry Sᵢⱼ quantifies the deviation of transaction j in dimension i from the normal low-rank structure. Common scoring strategies include:

• Row-wise L1 norm: Sum absolute sparse values per transaction to rank overall anomalousness
• Column-wise L1 norm: Identify features most frequently corrupted across transactions
• Thresholding on S: Flag entries where |Sᵢⱼ| > λ · σ, where σ is estimated noise level
• Dynamic thresholding: Adapt thresholds based on rolling statistics of S norms This interpretable scoring contrasts with black-box deep learning methods, allowing fraud investigators to trace exactly which features contributed to an alert and why a transaction was flagged.

Two primary formulations address different noise regimes:

• Standard RPCA (PCP): Assumes L is exactly low-rank and S is exactly sparse with no additional dense noise. Solves min ||L||* + λ||S||₁ subject to X = L + S
• Stable RPCA: Accommodates dense Gaussian noise N via X = L + S + N, solving min ||L||* + λ||S||₁ + (μ/2)||X - L - S||²_F. This is more realistic for financial data where transaction amounts have inherent measurement noise
• Parameter λ: Typically set to 1/√max(m,n) for theoretical guarantees, but cross-validated in practice on held-out normal periods
• Outlier pursuit: A variant where S is constrained to have sparse columns rather than sparse entries, ideal when entire transactions (not individual features) are anomalous

Batch RPCA requires the full data matrix, but financial fraud detection demands near-real-time processing. Extensions include:

• Online RPCA: Processes transactions sequentially, updating L and S estimates via stochastic optimization without storing the entire history
• Recursive Projected Compressed Sensing (ReProCS): Designed for video surveillance but adapted to streaming transaction data with slowly changing low-rank structure
• Grassmannian Rank-One Update Subspace Estimation (GROUSE): Incrementally updates the low-rank subspace as new normal transactions arrive
• Sliding window approaches: Apply batch RPCA to a rolling window of recent transactions, recomputing decomposition every N new observations These methods trade some decomposition accuracy for the ability to score transactions within milliseconds of arrival.