Search papers, labs, and topics across Lattice.
This paper analyzes the computational cost of three methods for updating matrix inverses in the context of online outlier detection using the Christoffel function: Direct Inversion (DI), Iterative Sherman-Morrison (ISM), and Woodbury Matrix Identity (WMI). Through theoretical analysis and Python simulations, the authors derive a quantitative rule for selecting the optimal method based on the rank of the update and the matrix size. They find that ISM is best for rank-1 updates, WMI for small updates relative to matrix size, and DI otherwise, providing a practical guideline for efficient online matrix inversion.
Forget brute-force inversion: this study reveals a simple rule for choosing the fastest matrix update method in streaming outlier detection, slashing computation time.
Outlier detection identifies data points that deviate significantly from expected patterns, revealing anomalies that may require special attention. Incorporating online learning further improves accuracy by continuously updating the model to reflect the most recent data. When employing the Christoffel function as an outlier score, online learning requires updating the inverse of a matrix following a rank-k update, given the initial inverse. Surprisingly, there is no consensus on the optimal method for this task. This technical note aims to compare three different updating methods: Direct Inversion (DI), Iterative Sherman-Morrison (ISM), and Woodbury Matrix Identity (WMI), to identify the most suitable approach for different scenarios. We first derive the theoretical computational costs of each method and then validate these findings through comprehensive Python simulations run on a CPU. These results allow us to propose a simple, quantitative, and easy-to-remember rule that can be stated qualitatively as follows: ISM is optimal for rank-1 updates, WMI excels for small updates relative to matrix size, and DI is preferable otherwise. This technical note produces a general result for any problem involving a matrix inversion update. In particular, it contributes to the ongoing development of efficient online outlier detection techniques.
