Matrix decomposition minimizing infinity norm

Question

I have the following minimization problem in diagonal matrix $D$ and matrix $V$

$$\text{minimize} \quad \| A - V D V^T \|_{\infty}$$

where square matrix $A$ is given. What approach should I take?

Answer 1

I'm assuming that you're interested in real matrices $A$ because of the use of transpose (rather than the Hermitian conjugate) in your statement of the problem.

This problem can be reduced to solving a linear programming problem and diagonalizing an $n$ by $n$ matrix.

If $A$ is symmetric, then $A$ can be diagonalized as

$A=VDV^{T}$

where $D$ is the diagonal matrix of eigenvalues of $V$ and $V$ is an orthogonal matrix of eigenvectors. So, you can reduce $\| A -VDV^{T} \|_{\infty}$ to 0 in this case.

If $A$ is not symmetric, then your problem can be written as

$\min_{B \in S^{n}} \| A - B \|_{\infty}$

where $S^{n}$ is the space of symmetric matrices. To get $V$ and $D$ from $B$, simply diagonalize $B$. Since the infinity norm of a matrix is the maximum of the row-wise sums of absolute values, this problem can be written as

$\min_{B \in S^{n}} \max_{i} \sum_{j=1}^{n} | A_{i,j}-B_{i,j} |$

Using standard techniques, we can reformulate this as a linear programming problem. First, we reduce the inner $\max$:

$\min_{B \in S^{n}} t_{0}$

subject to

$t_{0} \geq \sum_{j=1}^{n} | A_{i,j}-B_{i,j} |,\;\; i=1, 2, \ldots, n$

Next, we deal with the absolute value of $A_{i,j}-B_{i,j}$ by writing the problem as

$\min_{B \in S^{n}} t_{0}$

subject to

$t_{0} \geq \sum_{j=1}^{n} t_{i,j},\;\; i=1, 2, \ldots, n$

$t_{i,j} \geq A_{i,j}-B_{i,j},\;\; i=1, 2, \ldots, n, \; j=1, 2, \ldots, n.$

$t_{i,j} \geq -(A_{i,j}-B_{i,j}),\;\; i=1, 2, \ldots, n, \; j=1, 2, \ldots, n.$

Finally, we can rewrite the $B \in S^{n}$ constraints to get:

$\min_{B,t} t_{0}$

subject to

$t_{0} \geq \sum_{j=1}^{n} t_{i,j},\;\; i=1, 2, \ldots, n$

$t_{i,j} \geq A_{i,j}-B_{i,j},\;\; i=1, 2, \ldots, n, \; j=1, 2, \ldots, n.$

$t_{i,j} \geq -(A_{i,j}-B_{i,j}),\;\; i=1, 2, \ldots, n, \; j=1, 2, \ldots, n.$

$B_{i,j}=B_{j,i},\;\; i \neq j$.

This is an LP with $n^{2}+n+1$ variables and $n(n=1)/2+2n^{2}+n$ constraints.

You can also use the fact that $B_{i,j}=B_{j,i}$ to reduce the number of variables to $n(n+1)/2+n+1$ and eliminate $n(n-1)/2$ of the constraints.

Once you've found an optimal $B$, diagonalize $B$ to obtain $D$.