On the convexity of element-wise norm 1 of the inverse

Question

Question first asked on math.stackexchange here: https://math.stackexchange.com/questions/317209/on-the-convexity-of-element-wise-norm-1-of-the-inverse

On the convexity of element-wise norm 1 of the inverse

Let us define $\|A\|_1$ the element wise norm 1 of a matrix $A \in \mathbb{R}^{n \times m}$ as $$\|A\|_1=\sum_{i,j} |A_{i,j}| $$

Obviously, this function is convex over $\mathbb{R}^{n \times m}$. Is it true that the function $f:S^n_{++} \longrightarrow \mathbb{R}$, defined as $f(A) = \|A^{-1}\|_1$, is convex? Here we denote with $S^n \supset S^n_+ \supset S^n_{++}$ respectively the set of Symmetric, Positive Semidefinite (PSD) and Positive Definite (PD) $n \times n$ matrices.

Some observations:

Unfortunately matrix inversion is convex with respect to $S_+$, while $\|.\|_1$ is non decreasing with respect to the cone $R^{n \times m}_+$ and not with respect to $S_+$ (it is easy to find counterexamples). Hence theorems on combination of convex functions are not applicable.

I have tried to formulate function $f$ as $max\{ \ trace(M_i A^{-1}) \ \}_{i\in\mathcal{I}}$ where the $M_i\in S^n$ live in a family of matrices with elements equal to 1 or -1 so as to cover all the possible combinations of signed sums of elements of $A^{-1}$ but unfortunately not all such $M_i$ are PSD and therefore not all $trace(M_i A^{-1})$ are convex in $A$. Therefore I was not able to define $f$ as the pointwise max of convex functions.

I have also tried to consider $$ \|A^{-1}\|_1= \sum_{i,j}=\frac{|\det A_{\hat{\imath}\hat{\jmath}}|}{detA} $$ where $\det A_{\hat{\imath}\hat{\jmath}}$ is the minor associated to the $n-1 \times n-1$ sub-matrix obtained by eliminating row $i$ and column $j$ from $A$. But I have no intuition on how to go further...

Any thought?

Answer 1

The answer is Yes when $n=2$,but No when $n\ge3$. Here is the analysis.

The differential $L_A$ of $A\mapsto A^{-1}$ is $L_A=-A^{-1}BA^{-1}$. Likewise, the Hessian is $$H_A[B]=2A^{-1}BA^{-1}BA^{-1}=\frac2{(\det A)^3}\hat A B\hat AB\hat A,$$ where $\hat A$ is the adjugate matrix (mind that $A$ being symmetric, $(\det A)A^{-1}=\hat A$). Finally, the Hessian of the norm of $A^{-1}$ is $$\phi_A[B]=\frac2{(\det A)^3}\sum_{i,j}{\rm sgn}(\hat a_{ij})(\hat A B\hat AB\hat A)_{ij}.$$ For the function to be convex over $S_n^{++}$, it is therefore necessary and sufficient (the singular part of the Hessian, located at matrices such that some entry of $A^{-1}$ vanishes, is positive) to have, for every $S\in S_n^{++}$ and $B\in Sym_n$ $$\sum_{i,j}{\rm sgn}(s_{ij})(SBSBS)_{ij}\ge0.$$

When $B$ runs over $Sym_n$, $S^{1/2}BS^{1/2}$ covers $Sym_n$, and its square covers $S_n^+$. Thus $SBSBS$ runs over $S_n^+$. We infer that the convexity is equivalent to the property that for every $S\in S_n^{++}$ and $K\in S_n^+$, there holds $$\sum_{i,j}\epsilon_{ij}k_{ij}\ge0,$$ where $\epsilon(S):=(({\rm sgn}(s_{ij}))_{i,j}$. This amounts to saying that the matrix $\epsilon(S)$ is positive semi-definite.

This inequality turns out to be true if $n=2$, because $$\epsilon(S)=\begin{pmatrix} 1 & \pm1 \\\\ \pm1 & 1 \end{pmatrix}.$$ But this is false if $n\ge3$. Take for instance a matrix $A$ such that $S$, thus $(\det A)A^{-1}$, be a small disturbance of $I_3$, with negative off-diagonal entries. Then $$\epsilon(S)=\begin{pmatrix} 1 & -1 & -1 \\\\ -1 & 1 & -1 \\\\ -1 & -1 & 1 \end{pmatrix}$$ is indefinite.

Answer 2

The function that you have is convex for unitarily invariant norms, but for the (basis dependent) elementwise absolute value, it can clearly break as a trivial counterexample below shows.

\begin{equation*} X = \begin{pmatrix} 2 & 0 & 0\\\\ 0 & 1 & 0\\\\ 0 & 0 & 1 \end{pmatrix},\qquad Y = \begin{pmatrix} 10 & 9 & 5\\\\ 9 & 10 & 5\\\\ 5 & 5 & 4 \end{pmatrix} \end{equation*}

Now, simply define $Z = 0.5(X+Y)$, and consider $g(H)=\|H^{-1}\|_1$ as your function. Then, we see that $g(Z) = 3.1692$, while $0.5(g(X)+g(Y)) = 3$, clearly violating convexity.