Can I swap one matrix norm with another?
Some matrix norms are significantly costlier than others. For example, the matrix-2 norm requires computation of eigenvalues, whereas the matrix-1 norm is simply computed by finding the column of the matrix with the largest (absolute) sum (p283 of Carl D. Meyer).
Thus, the following question becomes relevant: Can we use some matrix norm in place of some other norm? Fortunately, for some applications, we can do this.
First of all, for analyzing limiting behavior, it makes no difference whether we use any of the following norms (see Exercise 5.12.3 of Carl D. Meyer):
- 1-norm
- 2-norm
- $\infty$-norm
- Frobenius norm.
In other words, if a sequence of matrices $\{A_k\}_k$ converges w.r.t. a given matrix norm, then they converge w.r.t. any of the norms above. Thus, for example, we do not have to rely on the computationally costly 2-norm but can use any other. This is possible because a specific norm of a matrix $||A||_i$ is bounded above by another norm multiplied by a constant coefficient. For example, for square matrices of size $n\times n$, it holds that (see p425, Exc 5.12.3 of Carl D. Meyer for more):
- $||A||_1\leq \sqrt{n} ||A||_2$
- $||A||_1\leq n ||A||_\infty$
- $||A||_2\leq ||A||_F$
- $||A||_F\leq \sqrt{n}||A||$
This brings us to a second case where we can make use of one matrix norm instead of another: If we are just interested whether the norm of a matrix exceeds a certain value or not, using a cheaply computed upper bound (e.g., 1-norm, Frobenius norm or $\infty$-norm). For example, in a Branch & Bound optimization scheme, we can eliminate a large sets of candidates for the solution via upper and lower bounds. Admittedly, the bounds can be too relaxed for large $n$. If one is interested in computing in sharper bounds for the 2-norm of a matrix (which is the computationally most involved in the list above), one should consider using the Gerschgorin circles.
