= Elliptical potential bound
{title2=$\sum_{t=1}^n x_t^TV_{t-1}^{-1}x_t\leq2\log(\det V_n/\det V_0)$}
Let $V_t=V_{t-1}+x_tx_t^T$ with <positive-definite matrix> $V_0$, and suppose $u_t=x_t^TV_{t-1}^{-1}x_t\leq1$. The <matrix determinant lemma> gives $\det V_t/\det V_{t-1}=1+u_t$. Since $2\log(1+u)-u$ has nonnegative derivative $(1-u)/(1+u)$ for $0\leq u\leq1$, summation proves the displayed bound. In particular, $V_0=\lambda I$, $\lambda\geq1$, and $\|x_t\|_2\leq1$ ensure $u_t\leq1$. Without that restriction a general form is $\sum_t\min\{1,u_t\}\leq2\log(\det V_n/\det V_0)$: for $u\geq1$, $2\log(1+u)\geq2\log2\geq1$. The bound connects widths of <confidence ellipsoids> to growth of a <determinant>.
Back to article page
