Robust Kronecker Component Analysis

Mehdi Bahri, Yannis Panagakis, Stefanos Zafeiriou

TL;DR

Robust Kronecker Component Analysis (RKCA) is a new framework for learning compact, low-rank representations of tensor data that is resilient to heavy noise and outliers. By combining the strengths of robust PCA and separable dictionary learning, it offers a scalable and theoretically grounded way to denoise, complete, and analyze high-dimensional visual data like images and videos.

What Problem Does This Paper Address?

Modern data is often high-dimensional and structured as tensors (multi-way arrays). Traditional methods for analyzing this data face a "double bind":

  1. Scalability vs. Structure: Standard "flat" methods like PCA or K-SVD often ignore the multi-dimensional structure of images, leading to massive computational costs and a loss of spatial correlation.
  2. Robustness: Most dictionary learning techniques are fragile; a few "bad" pixels (outliers) or missing values can completely derail the model.

While Robust PCA (RPCA) was designed to handle outliers, it doesn't learn a structured dictionary that can be easily reused or that respects the inherent separability of the data (e.g., the fact that an image has distinct horizontal and vertical dimensions). RKCA bridges this gap by providing a model that is simultaneously robust, structured, and computationally efficient.

Methods

The authors propose a structured tensor factorization model: $\mathcal{X} = \mathcal{R} \times_1 \mathbf{A} \times_2 \mathbf{B} + \mathcal{E}$.

  • Separability: Instead of one giant dictionary, the model learns two smaller bases ($\mathbf{A}$ and $\mathbf{B}$) whose Kronecker product forms the full dictionary. This "separable" approach drastically reduces the number of parameters.
  • Robustness: A sparse error term ($\mathcal{E}$) explicitly captures gross corruption, such as "salt and pepper" noise or occlusions, separating it from the clean, low-rank signal.
  • Optimization: The authors derive efficient solvers using the Alternating Direction of Multipliers Method (ADMM). To handle large-scale data, they introduce a Linearized ADMM (LADMM) variant that avoids solving expensive sub-problems.
  • Global Optimality: A major theoretical contribution is proving that for certain "degree 3" regularizers, their non-convex optimization problem actually has no spurious local minima—meaning any local solution found by the algorithm is a global optimum.

Datasets

The model was evaluated across several diverse benchmarks:

  • Synthetic Data: Used to verify the algorithm's ability to recover exact ranks and handle varying noise densities.
  • Background Subtraction: The Highway and Airport Hall video datasets, where the goal is to separate a static background from moving foreground objects.
  • Monochromatic Face Denoising: The Extended Yale-B dataset, consisting of face images under 64 different lighting conditions.
  • Color Image Denoising: The Facade image, chosen for its complex geometric patterns.
  • Image Completion: The 300 Faces in the Wild (300W) dataset, used to test the model's ability to "fill in" missing parts of faces caused by occlusions.

Key Insights and Ideas

  • Structure as Regularization: RKCA doesn't just rely on mathematical penalties (like the nuclear norm) to enforce low-rankness; it uses the factorized structure of the model itself to bound the rank, making it more "informed" than generic methods.
  • The "Double Perspective": The authors show that RKCA can be viewed either as a robust version of separable dictionary learning or as a structured, factorized version of Robust PCA. This allows them to draw on theoretical tools from both fields.
  • Scalability through Math: By leveraging the properties of the Kronecker product, the algorithm performs computations on much smaller matrices, allowing it to process high-resolution images that would crash standard matrix-based RPCA.
  • Theoretical Reliability: By connecting their work to recent advances in tensor factorization theory, they provide a rare guarantee of global optimality for a non-convex problem.

Key Results

  • Superior Denoising: In extreme noise conditions (e.g., 60% corruption), RKCA significantly outperformed state-of-the-art tensor methods (like HORPCA and TRPCA) in both visual quality and quantitative metrics (PSNR and FSIM).
  • Robust Background Subtraction: On the challenging Airport Hall dataset, RKCA achieved a top-tier AUC score of 0.88, proving highly effective at ignoring "ghosting" artifacts from immobile people that tripped up other algorithms.
  • Face Completion: RKCA was the only method among those tested that could successfully reconstruct faces with large self-occlusions in the 300W dataset, where standard matrix-based completion failed.

Limitations and Future Work

The authors acknowledge that while the "degree 2" regularizer is the most practical and easiest to tune, the "global optimality" proof currently only applies to the more complex "degree 3" version.

Future directions include:

  • Supervised RKCA: Adapting the model for specific tasks like classification or facial expression recognition.
  • Non-convex Regularizers: Exploring $L_p$ "pseudo-norms" to further sharpen the recovery of sparse and low-rank components.
  • Deep Learning Integration: Replacing the linear factorization with deep auto-encoders while maintaining the robust, multi-way tensor structure.

Summary updated

Abstract

Dictionary learning and component analysis models are fundamental for learning compact representations that are relevant to a given task (feature extraction, dimensionality reduction, denoising, etc.). The model complexity is encoded by means of specific structure, such as sparsity, low-rankness, or nonnegativity. Unfortunately, approaches like K-SVD - that learn dictionaries for sparse coding via Singular Value Decomposition (SVD) - are hard to scale to high-volume and high-dimensional visual data, and fragile in the presence of outliers. Conversely, robust component analysis methods such as the Robust Principal Component Analysis (RPCA) are able to recover low-complexity (e.g., low-rank) representations from data corrupted with noise of unknown magnitude and support, but do not provide a dictionary that respects the structure of the data (e.g., images), and also involve expensive computations. In this paper, we propose a novel Kronecker-decomposable component analysis model, coined as Robust Kronecker Component Analysis (RKCA), that combines ideas from sparse dictionary learning and robust component analysis. RKCA has several appealing properties, including robustness to gross corruption; it can be used for low-rank modeling, and leverages separability to solve significantly smaller problems. We design an efficient learning algorithm by drawing links with a restricted form of tensor factorization, and analyze its optimality and low-rankness properties. The effectiveness of the proposed approach is demonstrated on real-world applications, namely background subtraction and image denoising and completion, by performing a thorough comparison with the current state of the art.
BibTeX
@article{bahri2019robust,
  author = {Mehdi Bahri and Yannis Panagakis and Stefanos Zafeiriou},
  title = {{Robust Kronecker Component Analysis}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2019},
  url = {https://openreview.net/forum?id=7nHICZ8i-4},
}

Loading related content...

Figure