Cost Trade-offs in Matrix Inversion Updates for Streaming Outlier Detection

Florian Grivet; Louise Travé-Massuyès

cs.LGMar 17, 2026

Cost Trade-offs in Matrix Inversion Updates for Streaming Outlier Detection

Authors: Florian Grivet, Louise Travé-Massuyès

Organizations: CNES, 18 Av. Edouard Belin, Toulouse, 31400, Toulouse, France · LAAS-CNRS, University of Toulouse, CNRS, 7 Av. du Colonel Roche, 31400, Toulouse, France

Abstract

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.

Figures & tables

	DI ( Algorithm 1 )	ISM ( Algorithm 2 )	WMI ( Algorithm 3 )
Computational cost	$O\left(\frac{5}{6}s^{3}\right)+2ks^{2}$ ( 18 )	$4ks^{2}+2ks$ ( 24 )	$4ks^{2}+(4k^{2}-2k)s+O\left(\frac{5}{6}k^{3}\right)$ ( 27 )

Table 1: Computational cost of the three compared methods (in flops )

Panel of Figure 1 — Figure 1: Theoretical representation of thresholds from which choosing DI over ISM or WMI

	DI over ISM	DI over WMI	Empirical DI over WMI
$k$	${5s^{2}}/({12(s+1)})$ ( 28 )	$\frac{5}{6}k^{3}+4sk^{2}+$ $2(s^{2}-s)k-\frac{5}{6}s^{3}>0$ ( 29 , to solve with $s$ fixed)	$s/3.7506$ ( 30 )

Table 2: Theoretical thresholds for choosing the DI method over the ISM or WMI methods

Table 4

	DI over ISM	DI over WMI	Empirical DI over WMI
$k_{theoretical}$	$\eqref{eq:inversion_over_sherman}=\frac{5\times 1287^{2}}{12(1287+1)}\approx 535.834$	$\eqref{eq:inversion_over_woodbury}\approx 343.250$	$\eqref{eq:empirical_inversion_over_woodbury}=\frac{1287}{3.7506}\approx 343.145$
$k_{experimental}$	Between $10$ and $20$	Between $400$ and $500$

Table 5: Thresholds for choosing the DI method over the ISM or WMI methods with

s=1287

d=8

and

n=5

Figure 2: Fastest method for each (s, k) pair based on execution time

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Representation of the product of a row-vector by a column-vector

Panel of Figure 4 — Figure 4: Representation of the product of a column-vector by a row-vector

Panel of Figure 5 — Figure 5: Representation of the product of a row-vector by a matrix

Panel of Figure 6 — Figure 6: Representation of the product of a matrix by a column-vector

Panel of Figure 7 — Figure 7: Representation of the product of a matrix by a matrix

Online Anomaly Detection

Online anomaly detection identifies unusual events in data streams as they arrive, adapting to changing conditions while balancing detection speed, accuracy, and false alarms.

See all 57 papers

Efficient Online Inverse Optimization with $O(d)$ Regret
Sep 11, 2026Yang Cai, Anupam Gupta, Vineet Gupta +7
Google Research · Yale University · New York University +1
Outlier-Robust Diffusion Solvers for Inverse Problems
May 10, 2026Yang Zheng, Jiahua Liu, Tongyao Pang +2Diffusion Models for Image Restoration Robust Optimization
School of Computer Science and Engineering, University of Electronic Science and Technology of China · Yau Mathematical Sciences Center, Tsinghua University
Inference of Online Newton Methods with Nesterov's Accelerated Sketching
Apr 25, 2026Haoxuan Wang, Xinchen Du, Sen NaStochastic Approximation Second-Order Optimization
School of Industrial and Systems Engineering, Georgia Institute of Technology.

Sep 11, 2026J/K move · Enter open · S save

Efficient Online Inverse Optimization with $O(d)$ Regret

Yang Cai, Anupam Gupta, Vineet Gupta, Guru Guruganesh+6

Google Research · Yale University · New York University+1

Open paper AskPDF arXiv

We give a deterministic algorithm for online inverse linear optimization with regret

O(d)

, uniform in the horizon and

O(d^{2})

time per round. A bound of this order was obtained recently by Dewasurendra, settling a question of Gollapudi et al.\ and of Oki and Sakaue, but by an improper rule that enumerates covers at every scale and costs

T^{Θ(d)}

a round; ours is the first efficient such bound and the first proper one. We build on the variable-metric framework of Sakaue et al., adding a self-normalized rank-one update, and we replace the

\log\det

potential by the trace power

\tr(H^{-1/2})

, which is bounded outright and removes the

\ln T

. The bound also holds against an expert that does not optimize, and we give corruption-robust and rank-adaptive variants, and an application to convex minimization.

Abstract

Online Anomaly Detection

Explore similar work

Efficient Online Inverse Optimization with O(d)O(d)O(d) Regret

Outlier-Robust Diffusion Solvers for Inverse Problems

Inference of Online Newton Methods with Nesterov's Accelerated Sketching

Efficient Online Inverse Optimization with $O(d)$ Regret