Bound on the condition number of a PSD matrix

Question

Suppose $x_s$ is a $d$ dimensional vector which are features in the regression model. Values in the vector $x_s$ are controlled or uncontrolled. For example, the first element might be chosen by a person, so it is not randomly selected. We define $\mathbf{V}=\sum_{s=1}^{t}\mathbf{x}_s \mathbf{x}_s^\top + \lambda \mathbf{I}$ (design matrix in regression) where $\lambda$ is a positive scalar. Assuming that $l \le \| \mathbf{x}_s\| \le L$, how is it possible to find an upper bound on the condition number of the matrix $\mathbf{V}$?

Answer 1

Since $\sum_sx_sx_s^T$ is positive semidefinite, the minimum possible eigenvalue of $V$ is $\lambda$. Also, we have $$ \begin{aligned} \lambda_\max(V) &=\lambda+\lambda_\max(\sum x_sx_s^T)\\ &\le\lambda+\|\sum_sx_sx_s^T\|_F\\ &\le\lambda+\sum_s\|x_sx_s^T\|_F\\ &=\lambda+\sum_s\|x_s\|^2\\ &\le\lambda+tL^2. \end{aligned} $$ Therefore the condition number of $V$ with respect to the induced $2$-norm, namely $\kappa(V)=\frac{\lambda_\max(V)}{\lambda_\min(V)}$, is bounded above by $\frac{\lambda+tL^2}{\lambda}$. This upper bound is sharp if $d>1$. It is attained when all $x_s$s are the same vector with norm $L$.