Constant to bound Frobenius norm

Question

Suppose $X \in {\Bbb R}^{{n \times p}}$ and $\beta, \beta^{\star} \in {\Bbb R}^{p \times 1}$. Can we give a bound for $C$ such that the inequality

$$ \left\| X (\beta - \beta^*) \right\|^2_F \leq C \left\| \beta - \beta^* \right\|^2_F$$

holds?

Answer 1

Let $v = \beta - \beta^*$. Your inequality is equivalent to saying that either $\|v\| = 0$ or $$ \frac{\|Xv\|}{\|v\|} \leq C. $$ Suppose then that we were to look for the best such bound. In particular, we would take $C$ to be $$ C := \max_{v \in \Bbb R^{p \times 1},\, v \neq 0} \frac{\|Xv\|}{\|v\|}. $$ As it turns out, this maximimum is guaranteed to exist and is precisely the definition of the spectral norm of $X$. In particular, we can guarantee that your inequality holds for all choices $\beta,\beta^*$ if and only if $C \geq \|X\|_2$, where $\|X\|_2$ denotes the spectral norm.

As it turns out, this quantity can be relatively easily computed. In particular we have $$ \|X\|_2 = \sigma_{\max}(X) = \sqrt{\lambda_{\max}(X^TX)} $$ where $\sigma_\max$ here denotes the maximal singular value and $\lambda_{\max}$ denotes the maximal eigenvalue.