Upper bound on a norm of a vector w.r.t a positive definite matrix

Question

Suppose $\mathbf{z}_s \in \mathbb{R}^d$ for all $s\in\{1,\cdots,t \}$ such that $l\le \|\mathbf{z}_s \|\le L$. We define $\mathbf{V}_t = \sum_{s=1}^t \mathbf{z}_s \mathbf{z}_s^\top + \lambda \mathbf{I}$ which is the design matrix in linear regression. I am wondering if it is positive to find an upper bound on $\|\mathbf{z}_t \|_{\mathbf{V}_t^{-1}}$ based on the value of $t$ and other parameters?

Answer 1

A sharp upper bound is given by $\sqrt{\frac{L^2}{L^2+\lambda}}$. It is attained when $\|\mathbf z_t\|=L$ and $\mathbf z_t$ is orthogonal (with respect to the standard inner product) to all other $\mathbf z_j$s.

Let $Z\in\mathbb R^{d\times t}$ be the matrix whose $j$-th column, for each $j$, is equal to $\mathbf z_j$. By a change of orthonormal basis, we may assume that $\mathbf z_t=(a,0,\ldots,0)^\top$ for some $a\in[l,L]$. Using Schur complement, we see that the $(1,1)$-th element of $ZZ^\top+\lambda I$ is equal to $\big((ZZ^\top)_{11}+\lambda-p\big)^{-1}$ for some nonnegative number $p$. Therefore $$ \|\mathbf z_t\|_{V_t^{-1}} =\sqrt{\mathbf z_t^\top V_t^{-1}\mathbf z_t} =\sqrt{\frac{a^2}{(ZZ^\top)_{11}+\lambda-p}} \le\sqrt{\frac{a^2}{a^2+\lambda}} \le\sqrt{\frac{L^2}{L^2+\lambda}}. $$