Certifiably Optimal Low Rank Factor Analysis

Dimitris Bertsimas, Martin S. Copenhaver, Rahul MazumderJMLR 2017

TL;DR

This paper introduces a novel framework for Factor Analysis (FA) that guarantees provably optimal solutions for approximating covariance matrices with low-rank structures. By reformulating the problem as a smooth optimization problem with convex constraints and employing advanced optimization techniques, the authors achieve state-of-the-art accuracy and scalability, enabling more interpretable insights from complex datasets.

What Problem Does This Paper Address?

Factor Analysis (FA) is a cornerstone technique in statistics, psychometrics, and econometrics, used to uncover underlying latent factors that explain the relationships among observed variables. A core FA model decomposes a covariance matrix ($\Sigma$) into a low-rank positive semidefinite (PSD) component ($\Theta = LL^T$) representing common factors and a diagonal matrix ($\Phi$) representing unique variances. The challenge lies in finding $\Theta$ and $\Phi$ such that $\Sigma = \Theta + \Phi$, with $\Theta$ being low-rank and $\Phi$ having non-negative diagonal entries, and crucially, $\Sigma - \Phi$ being PSD. This PSD constraint on the residual covariance matrix is vital for statistical interpretability, allowing for meaningful analysis of explained variance.

However, traditional FA methods often struggle with this constraint, leading to issues like "Heywood cases" (negative unique variances) or indefinite residual covariance matrices, which hinder interpretation. Furthermore, the rank constraint on $\Theta$ makes the optimization problem non-convex, posing significant computational challenges for finding globally optimal solutions, especially for high-dimensional data. This paper addresses the need for a method that can find certifiably optimal solutions to this rank-constrained FA problem, offering both computational efficiency and statistical interpretability.

Methods

The authors propose a flexible family of rank-constrained, nonlinear Semidefinite Optimization (SDO) formulations for FA. A key contribution is an exact reformulation of the rank-constrained problem into a smooth optimization problem with convex, compact constraints. This reformulation, particularly for the case $q=1$ (related to the Schatten 1-norm), is shown to be equivalent to Approximate Minimum Rank Factor Analysis (MRFA).

They develop a unified algorithmic framework that combines:

  • Nonlinear Optimization: Utilizing techniques like the Conditional Gradient (CG) algorithm to find stationary points of the reformulated problem.
  • Convex Optimization: Employing first-order methods to solve the convex SDO subproblems that arise at each iteration of the CG algorithm.
  • Discrete and Global Optimization: Incorporating branch-and-bound techniques to provide certifiable lower bounds and prove optimality for the solutions found. This includes developing novel approaches for computing convex envelopes and utilizing Weyl's inequality for bound tightening and pruning.

The proposed method is designed to be scalable, capable of handling covariance matrices with thousands of variables, a significant improvement over previous methods that struggled with larger dimensions.

Datasets

The paper evaluates its proposed methods on:

  • Synthetic Datasets: Four classes of synthetic data (A1, A2, B1, B2, B3) are generated with varying structures of low-rank common factors and unique variances. These classes are designed to test different aspects of the FA problem, including exact low-rank structures, exponentially decaying eigenvalues, and structured common factor subspaces.
  • Real-world Datasets: The methods are tested on several benchmark datasets commonly used in FA research:
  • bfi data set (2800 observations, 28 variables)
    • neo data set (1000 observations, 30 variables)
    • Harman data set (correlation matrix of 24 psychological tests)
    • geomorphology data set (10 variables)
    • JO data set (24 observations, 58 variables, non-full rank correlation matrix)

Key Insights and Ideas

  • The Power of the PSD Constraint: The paper strongly emphasizes the statistical interpretability gained by enforcing the PSD constraint on $\Sigma - \Phi$. This constraint ensures that the residual covariance matrix is well-behaved, allowing for meaningful analysis of explained variance and avoiding issues like indefinite residual covariances.
  • Bridging Optimization Paradigms: A crucial insight is the successful integration of nonlinear optimization (for finding feasible solutions) with discrete and global optimization (for proving optimality). This hybrid approach allows for both computational efficiency and theoretical guarantees.
  • Certifiable Optimality for Intractable Problems: The paper demonstrates that a previously intractable rank-constrained optimization problem can be solved to provable optimality. This is a significant advancement, as such guarantees were previously difficult to obtain for FA.
  • Weyl's Inequality as a Practical Tool: The application of Weyl's inequality for computing lower bounds and pruning nodes in the branch-and-bound tree proves to be a computationally efficient and effective strategy, especially for problems with certain spectral properties.
  • Scalability Breakthrough: The proposed framework achieves unprecedented scalability for certifiably optimal low-rank FA, handling problems with thousands of variables, which opens up new avenues for analyzing large-scale datasets.

Key Results

  • Superior Performance: The proposed methods (CFAq) consistently outperform existing FA methods (MINRES, PA, WLS, GLS, MTFA, PC, MLE) across various performance metrics, including estimation error of $\Phi$, explained variance, and violation of the PSD constraint on $\Sigma - \Phi$.
  • Provable Optimality: The branch-and-bound algorithm successfully finds certifiably optimal solutions for problems of realistic sizes, often within minutes or hours, depending on the problem size and rank.
  • Computational Efficiency: The algorithms are scalable to thousands of variables, with computational bottlenecks (eigendecompositions) being manageable for modern hardware.
  • Improved Interpretability: The enforced PSD constraint on $\Sigma - \Phi$ leads to more statistically interpretable results, particularly in understanding the proportion of variance explained by latent factors.
  • Flexibility: The framework allows for controlling the complexity of the model through the choice of rank $r$ and the parameter $q$ in the Schatten norm, offering flexibility in exploratory FA.

Limitations and Future Work

  • Computational Cost of Optimality Proof: While feasible solutions are found quickly, proving optimality can still be computationally intensive, especially for larger ranks and problem sizes. The number of nodes explored in the branch-and-bound tree can grow significantly.
  • Branching Strategy Impact: The performance of the branch-and-bound algorithm is sensitive to the branching strategy. While a modified strategy using Weyl bounds shows improvement, further research into dynamic branching strategies could yield even better results.
  • Generalization to $q > 1$: While the framework is designed for $q \ge 1$, the paper focuses primarily on $q=1$ and $q=2$. Extending the computational analysis and theoretical guarantees for higher values of $q$ could be beneficial.
  • Non-convexity Challenges: The inherent non-convexity of the problem means that while the proposed methods find high-quality stationary points and can prove optimality, ensuring global optimality for all possible problem instances remains an active area of research in optimization.

The authors envision that the techniques developed in this paper can be extended to a broader class of matrix-structured estimation problems, suggesting significant progress in optimization and related fields in the coming decade.

Summary updated

BibTeX
@article{bertsimas2017certifiably,
  author = {Dimitris Bertsimas and Martin S. Copenhaver and Rahul Mazumder},
  title = {{Certifiably Optimal Low Rank Factor Analysis}},
  journal = {J. Mach. Learn. Res.},
  year = {2017},
}
Figure