[Math] Sup Norm of a Matrix

linear algebra

The matrices the sup norm defined for $n$-tuples. That is, if $A$ is a matrix of size $n$ by $m$ with general entry $a_ij$, we define

$$\left |A\right |=\max\left\{\left|a_{ij}\right|; \text{i=1,2,…,n and j=1,…,m} \right\}$$.

Question: Let $A=\begin{bmatrix} 1 & 2 \\ 1 & -3 \end{bmatrix}$ be a matrix. What is the $\left |A\right |$?

My answer is $3$,that is sup norm is maximum compenent of $A$ which is positive,right? Can you check? Thanks…

Best Answer

Your answer is correct. It's clear that $$ \vert A \vert = \max\{1,2,3 \} = 3. $$

Related Solutions

[Math] What does norm of a matrix mean

Given a vector norm $|\cdot|$ on $\mathbb{C}^n$ one defines the induced matrix norm as the largest value that $|Ax|$ can attain for a vector $x$ of norm $1$. Equivalenetly, one can define it as the largest value that $|Ax|/|x|$ can attain over all non-zero vectors (this is quite clearly the same).

Intuitively, this makes sense, since it measures by how much the matrix can change the size of a vector. Of course, one still needs to check this actually gives a norm.

This norm then has the nice property that $|Ay| \le ||A|| \ |y|$ for a matrix $A$ and a vector $y$, and also that $||AB|| \le ||A|| \ ||B||$ for two matrices $A,B$.

One can do this definition for any vector norm, there it is done with respect to the $2$-norm.

Another advantage is that this definition generalizes quite directly to linear operators on Banach spaces.

Solve matrix $2$-norm problem with diagonal matrix constraint

Partial answer for how to go about this numerically (since the objective function may not be everywhere differentiable it seems, so I'm not going to do it analytically).

This is an unconstrained convex optimization problem on $\mathbb{R}^n$. Furthermore, the objective $f$ follows the rules of so-called "Disciplined Convex Programming". Hence, convex optimization software such as CVXPY can handle it. Here's a short script in Python:

import cvxpy as cp
import numpy as np

def main():
    n = 10 # Require n > m 
    m = 5

    F = np.random.randn(n, m)
    A = np.random.randn(m, m)

    b = cp.Variable(n)

    objective = cp.Minimize(cp.norm(A - F.T * cp.diag(b) * F))

    prob = cp.Problem(objective, [])

    result = prob.solve(solver='SCS')

    print(b.value)
    print(result)

main()

(Sub)gradient descent approach

The function $f$ is differentiable at any point $b$ where the matrix $A-F^\text{T}\text{diag}(b)F$ has a unique largest singular value. At such a point, let $u$ and $v$ denote the left and right singular vectors (respectively) corresponding to the (unique) largest singular value. The gradient of $f$ at such a point is $$ \nabla{f}(b)=-Fu\otimes{Fv}, $$ where $\otimes$ denotes component-wise multiplication. At points where $f$ is isn't differentiable, you have to be more careful--look up subgradient descent. I'm not sure what kind of convergence guarantees there are for this, but it will be cheaper than CVXPY.

I implemented a simple version in Python, and my main issue was finding step-sizes that led to convergence--I got lots of oscillation.

Best Answer

Related Solutions

[Math] What does norm of a matrix mean

Solve matrix $2$-norm problem with diagonal matrix constraint

Related Question