Given any symmetric matrix $A$, how to find a diagonal matrix $B$ such that $B \succeq A$?

Question

Given any symmetric (not necessarily PSD) matrix $A$, how can we find a good diagonal matrix $B$ such that $A \preceq B$? We want each of the diagonal elements of $B$ to be as small as possible.

One possible such matrix I can think of is $\mathrm{diag}(\|A_i\|_1)$, but I don't think it is tight enough. Can we find a better matrix than this? Also, I hope that $B$ depends on the $\ell_2$ norms of $A_i$ instead of the $\ell_1$ norms, or the eigenstructure of the matrix $A$. It would be very useful if there are solutions that only needs eigenvalues or singular values, so it is possible to approximate it in almost linear time to the dimension.

The background for this problem is "coordinate-wise smoothness" in convex and non-convex optimization. The global smoothness of a function can be defined as $\sup\|\nabla^2f(x)\|_2$, that is to find a constant $L$ such that $-LI \preceq \nabla^2 f(x) \preceq LI$. I'm looking for a similar way to find the coordinate-wise smoothness efficiently.

Answer 1

Have you considered something like the following semidefinite program?

$$\begin{array}{ll} \underset{{\bf x}}{\text{minimize}} & \| {\bf x} \|_1\\ \text{subject to} & \mbox{diag} ({\bf x}) \succeq {\bf A}\end{array}$$

---

Experiments

Let

$$ {\bf A} := \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} $$

whose maximal eigenvalue is $\lambda_{\max} ({\bf A}) = 3$. Using CVXPY to solve the semidefinite program above,

from cvxpy import *
import numpy as np

A = np.array([[ 2, 1],
              [ 1, 2]])
   
# optimization variables
x = Variable(2)

# optimization problem
optProb  = Problem(Minimize(norm(x,1)), [ diag(x) >> A ])
optProb.solve()

# output
print("Status  = ", optProb.status)
print("Minimum = ", optProb.value )
print("      x = ",       x.value )

which outputs

Status  =  optimal
Minimum =  5.999999999483413
      x =  [3. 3.]

Note that ${\bf x} = \lambda_{\max} ({\bf A}) \, {\bf 1}_2$. Using ${\bf A} = \mbox{diag}(2,1)$ instead,

A = diag(np.array([2,1]))

the output is

Status  =  optimal
Minimum =  3.0000000000262323
      x =  [2. 1.]