5
$\begingroup$

I need to find an upper bound for a matrix norm in terms of bounds of its columns. I have a vector $\varepsilon_i(x) \in R^{n\times1} $ such that $||\varepsilon_i(x)||_2\le\gamma_0$. I also have a matrix $Z=[\varepsilon_1, \varepsilon_2, \varepsilon_3, ... ,\varepsilon_N] \in R^{n\times N}$.

Using the information $||\varepsilon_i(x)||_2\le\gamma_0$, can I find an upper bound for $||Z||_2$?

If this were to be a frobenius norm question, it would be quite easy to show. However, I couldn't find an inequality for L2 norm case.

Thank you in advance for your help.

$\endgroup$
1
  • $\begingroup$ you do have the inequality $||A||_2\leq||A||_F$. Furthermore this inequality is tight if $A$ is rank 1 or less, so I'm not sure you will be able to find a better bound without further information. $\endgroup$
    – Set
    Commented Feb 12, 2016 at 19:32

1 Answer 1

5
$\begingroup$

If you use the following definition for $\|Z\|_2$, where $Z\in\mathbb R^{n\times N}$ $$\|Z\|_2:=\sup\limits_{x\in \mathbb R^N}{\frac{\|Zx\|_2}{\|x\|_2}}$$ then you have $Zx=\sum\limits_{i=1}^{N}{x_i\epsilon_i}\Rightarrow \|Zx\|_2=\|\sum\limits_{i=1}^{N}{x_i\epsilon_i}\|_2\leq \sum\limits_{i=1}^{N}{|x_i|\|\epsilon_i\|_2}\leq \gamma_0\sum\limits_{i=1}^{N}{|x_i|}$ Also $\|x\|_2=\sqrt{x_1^2+...+x_N^2}\ge \frac{1}{\sqrt N}\sum\limits_{i=1}^{N}{|x_i|}$. So you get $$\frac{\|Zx\|_2}{\|x\|_2}\leq \gamma_0\frac{\sum\limits_{i=1}^{N}{|x_i|}}{\frac{1}{\sqrt N}\sum\limits_{i=1}^{N}{|x_i|}}=\gamma_0\sqrt N$$ Finally, $$\|Z\|_2=\sup\limits_{x\in \mathbb R^N}{\frac{\|Zx\|_2}{\|x\|_2}}\leq \gamma_0\sqrt N$$

$\endgroup$
2
  • $\begingroup$ So just to be clear, $\|x\|_2=\sqrt{x_1^2+...+x_N^2} \ge \frac{N}{\sqrt N} |x_1|$. So, $x_1$ is the largest scalar in the x vector and $\gamma_0$ is the largest of the column norms? $\endgroup$
    – Aditya P
    Commented Feb 18, 2021 at 8:11
  • 1
    $\begingroup$ @AdityaP No, I think I have a typo. In my opinion every $\epsilon_i$ is bounded by the same constant $\gamma_0$. So, wherever you see $x_1$, I think it should be $x_i$. $\endgroup$
    – Svetoslav
    Commented Feb 18, 2021 at 19:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .