An Approximate, Randomized 'Eigen' Algorithm

In the world of numerical algorithms, finding efficient solutions for matrix decomposition is a cornerstone of many scientific and engineering applications. Eigenvalue decomposition, in particular, plays a crucial role in fields ranging from signal processing to machine learning. One interesting challenge is developing approaches that are both computationally efficient and suitable for environments with constraints, such as embedded systems or real-time applications.

In this post, we explore an approximate, randomized algorithm for eigenvalue decomposition that leverages the "Follow the Perturbed Leader" (FPL) framework. This approach is particularly useful in scenarios where traditional sparse matrix packages may be too cumbersome to implement in constrained environments. By combining randomization techniques with iterative eigenvector computation methods, we aim to simplify the problem without sacrificing accuracy.

Background

In its linear, discrete-time form, Kalman filters can be described by the following equations:

$$\begin{array}{lcl}{x}_{t+1}& =& A{x}_t+w\\ y& =& C{x}_t+v\\ \left(\begin{array}{c}w\\ v\end{array}\right)& \sim & N(0,\left(\begin{array}{cc}{Q}_w& 0\\ 0& R_v\end{array}\right))\end{array}$$

In an ideal situation, covariance matrices $Q_w$ and $R_v$ are known. However, when empirical errors are not easily observable, as in cases with sensor calibration challenges, alternative methods must be employed, such as maximum likelihood estimation. This leads to a matrix optimization problem:

$$\begin{array}{l}\underset{R_w,Q_w}{min}(\ln det{P}_{R_w,Q_w}+Y^{\prime }{P}_{R_w,Q_w}^{-1}Y)\\ \text{s.t.}{Q}_w,R_w\ge 0\\ P_{R_w,Q_w}=\sum _{i=1}^{N+K-1}{\mathbb{O}}_i{Q}_w{\mathbb{O}}_i^{\prime }+\sum _{j=1}^N{\mathbb{I}}_j{R}_v{\mathbb{I}}_j^{\prime }\end{array}$$

One solution is to decompose $P$, either through Cholesky or other methods, keeping in mind that $P$ is often sparse.

The Algorithm

We propose a randomized matrix algorithm to approximate eigenvalue decomposition. In many cases, sparse matrix libraries are too large to fit into embedded systems, leading to implementation challenges. Our algorithm offers an alternative, balancing efficiency and accuracy.

This approach leverages the "Follow the Perturbed Leader" (FPL) oracle-based eigenvector computation in an online setting.

We assume we have a distribution $\mathcal{D}$ over ${\mathbb{S}}_n$, the set of symmetric matrices, and we express the matrix $A$, whose eigenvectors we seek, as a sum of (potentially sparse or random) matrices $A_{\tau }$. Rescaling by a constant does not affect the result.

The algorithm operates as follows:

$$\begin{array}{l}\mathbf{Algorithm}:\text{Follow the Perturbed Leader (FPL)}\\ \begin{array}{ll}1:& \text{Sample a matrix }N\sim \mathcal{D}.\\ 2:& x_1\leftarrow EV(N).\\ 3:& \mathbf{for}t=1,2,\dots \mathbf{do}\\ 4:& \text{Play }{x}_t\text{ and observe }{A}_t.\\ 5:& x_{t+1}\leftarrow EV(\sum _{\tau =1}^t{A}_{\tau }+N).\\ 6:& \mathbf{end}\mathbf{for}\end{array}\end{array}$$

An effective way of evaluating $N\sim \mathcal{D}$ is by drawing a vector $v$ of i.i.d. normals and computing $N=c\cdot v{v}^{\prime }$, with $c$ being a constant defined as $c=\sqrt{\frac{T}{n}max(1,\ln \frac{T}{n})}$.

Computing Approximate Eigenvectors

Assuming we wish to compute approximate eigenvectors and values of $A$, the algorithm proceeds as follows:

$$\begin{array}{ll}1:& \mathbf{for}i=1,\dots ,N\mathbf{do}\\ 2:& \text{Guess approximate leading eigenvector }{l}_i\text{ and eigenvalue }{\lambda }_i\text{ of }A\text{via the FPL algorithm}.\\ & \text{(Power method with orthonormalization steps)}.\\ 3:& A\leftarrow A-{\lambda }_i{l}_i{l}_i^{\prime }.\\ 4:& \mathbf{end}\mathbf{for}\end{array}$$

Conclusion

This randomized approach provides a practical solution for scenarios where traditional eigenvalue algorithms are computationally prohibitive or impractical for embedded applications. By applying FPL techniques, we can iteratively compute eigenvectors in an efficient, online setting.

References

• Identification of Disturbance Covariances Using Maximum Likelihood Estimation, Megan Zagrobelny et al., 2014
• Online Learning of Eigenvectors, Dan Garber et al., JMLR 2015