Partial eigendecompositions for rank-deficient matrices

[david-cortes-intel]

Note: this is a transcription from the docs section on ideas for contributors.

Some algorithms in oneDAL rely on spectral decompositions which are performed by calling corresponding routines from LAPACK for symmetric eigenvalue calculations - particularly function SYEVR. This function is always tasked with obtaining a full eigenvalue decomposition, but being a sequential procedure, it can also calculate partial eigencompositions - i.e. up to only the $N$ largest eigenvalues.

For many use-cases, components with too-small singular values in the resulting spectral decomposition are later on discarded, in line with other LAPACK procedures such as GELSD. It cannot be guaranteed without a prior decomposition of some kind that a symmetric matrix will have a minimum number of large-enough components, but it can be known apriori (before calling SYEVR) in some cases that a minimum number of eigenvalues should in theory be zero and thus should get discarded. In particular, a symmetric matrix $\mathbf{A}$ which is the cross-product of another matrix $\mathbf{X}$ can have a number of non-zero eigenvalues at most equal to the number of rows in the matrix $\mathbf{X}$.

Hence, if dealing with a rank-deficient matrix $\mathbf{A}$ - i.e. a matrix which is the cross-product of a matrix $\mathbf{X}$ which has more columns than rows - then it can be known apriori (before calling the SYEVR function) that some eigenvalues should in theory be zero or negative, and the SYEVR function call can be sped up by not calculating a full decomposition.

This would require keeping track of the number of rows in $\mathbf{X}$ that generated a given matrix $\mathbf{A}$throughout the procedures that use it, up until in reaches the SYEVR function call, which should be modified accordingly.

Algorithms that might perform eigendecompositions on rank-deficient matrices include:

• Linear models.
• PCA.
• Precision calculation in covariance.

Linear regression is currently implemented through a mechanism which first attemps a Cholesky decomposition, and falls back to eigenvalue decomposition when that fails, but for rank-deficient matrices, it will be known apriori that Cholesky will fail, so it can be skipped straight to eigendecomposition.