Matrix norm of product with diagonal does not factorize

linear algebramatricesmatrix-calculusnumerical linear algebranumerical methods

Let $\|\cdot\| : \mathbb{R}^{n\times n} \rightarrow \mathbb{R}_+$ be the operator norm w.r.t. the $2$-norm on $\mathbb{R}^n$.

Do you have a quick counterexample to disprove that
$$
\|\Lambda A\| = \|\Lambda\|\|A\| \quad \text{ for all diagonal } \Lambda\in\mathbb{R}^{n\times n}\ ?
$$

(Not a homework question.)

Best Answer

The answer is no. As a counterexample, consider $$ \Lambda = \pmatrix{1&0\\0&0}, A = \pmatrix{1 & 1\\ 1 & 1}. $$ We have $\|\Lambda\| = 1, \|A\| = 2, \|\Lambda A\| = \sqrt{2}$.

Related Solutions

[Math] Norm of Block Diagonal Matrix

Let $A=U\tilde{\Sigma}V^T$ be the SVD of the rank-$r$ matrix $A$ with $$ \tilde{\Sigma}=\begin{bmatrix}\Sigma_r&0_{r\times(n-r)}\\0_{(m-r)\times r}&0_{(m-r)\times(n-r)}\end{bmatrix}\in\mathbb{R}^{m\times n}, $$ where $\Sigma_r=\mathrm{diag}(\sigma_1,\ldots,\sigma_r)$ is diagonal with the nonzero singular values of $A$ on the diagonal. The matrix $M$ is orthogonally similar (hint: consider the block diagonal matrix with diagonal blocks $V$ and $U$) to $$ N=\begin{bmatrix} \alpha I_r & 0_{r\times(n-r)} & -\Sigma_r & 0_{r\times(m-r)} \\ 0_{(n-r)\times r} & \alpha I_{n-r} & 0_{(n-r)\times r} & 0_{(n-r)\times(m-r)} \\ -\Sigma_r & 0_{r\times(n-r)} & \beta I_r & 0_{r\times(m-r)} \\ 0_{(m-r)\times r} & 0_{(m-r)\times(n-r)} & 0_{(m-r)\times r} & \beta I_{m-r} \end{bmatrix}. $$ Now you can see the spectrum of $N$ (and hence the spectrum of $M$) consists of the eigenvalues of $2\times 2$ matrices $$ \begin{bmatrix} \alpha & -\sigma_i \\ -\sigma_i & \beta \end{bmatrix}, \quad i=1,\ldots,r. $$ The spectrum of $M$ may also contain $\alpha$ (if $r<n$) and/or $\beta$ (if $r<m$). From here, you can find your operator norm of $M$ (and $M^{1/2}$ as well).

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] Norm of Block Diagonal Matrix

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

Related Question