Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Question first asked on math.stackexchange here: http://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?

share|improve this question
    
What are $S_+$, $S_{++}^n$, and $S^n$? –  Mark Meckes Mar 19 '13 at 14:00

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
Sorry, I don't get your answer... 1) X is not symmetric, let alone positive definite, My question regarded exclusively PD matrices. 2) if with $f$ you mean the functional $f(A)=\|A^{-1}\|_1$, then $f(Z)=3.46 < 3.5 = \frac{1}{2} (f(X)+f(Y))$ which does not violate convexity –  Ferpect Mar 19 '13 at 17:36
    
Sorry, there was an obvious typo in there; of course, I mean hermitian positive def. matrices. Fixed now. –  Suvrit Mar 19 '13 at 20:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.