Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Some observation:

Unfortunately matrix inversion is $S_+$ - convex 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
    
Since all functions $A\mapsto \operatorname{trace}(MA^{-1})$ are convex in $A$, have you tried fixing such $M$ and experimenting with $A$ such that $\|A^{-1}\|_1=\operatorname{trace}(MA^{-1})$? –  user53153 Feb 28 '13 at 22:33
    
$A \rightarrow trace(MA^{-1})$ is convex on $S_{++}$ if and only if $M$ is PSD. For instance take $M$ equal to $-I_d$ where $I_d$ is the identity. then $-trace(A^{-1})$ is concave. –  Ferpect Feb 28 '13 at 22:38
    
Ah, but you only need to consider $M$ of the form $(\operatorname{sign}a_{ij})$ where $(a_{ij})$ is a positive definite matrix. This implies, in particular, that $M$ is symmetric and with $1$ on the diagonal... –  user53153 Feb 28 '13 at 22:43
    
yeah but take for example a 3x3 matrix that has all 1s on the diagonal and -1/2 over the other elements. That matrix is psd but its 'sign' matrix is not. –  Ferpect Feb 28 '13 at 22:49
    
Here is a rough idea which may or may not bear fruit: For $t \in [0,1]$, we have $(tS_1 + (1-t)S_2)^{-1} = S_1^{-1/2}U(tI + (1-t) \Lambda)^{-1} U^T S_1^{-1/2}$ where $S_1^{-1/2} S_2 S_1^{-1/2} = U \Lambda U^T$ with the RHS being the spectral decomposition and each of the matrix square-roots refers to the unique symmetric positive definite root. Then with $A = S^{-1/2} U$, we are interested in the convexity of $\|A(t I + (1-t) \Lambda)^{-1} A^T\|_1$. I have not tried, but maybe some consistency of the $1$-norm comes into play or something similar. –  cardinal Mar 11 '13 at 3:44
add comment

2 Answers

Here is a counterexample for $n \geq 3$. It is enough to show that $f$ is not convex along a rank-1 direction. Let $x \in \mathbb{R}^n$ with $\lVert x \rVert = 1$ and consider the function $$g(t) = \lVert (I + t xx^T)^{-1} \rVert_1 \,, t \geq 0 \,.$$ By the matrix inversion lemma, $$ (I + t xx^T)^{-1} = I - \frac{t}{1 + t} xx^T \,. $$ Note that the diagonals of the above matrix are non-negative. Then $$ g(t) = n + \alpha \frac{t}{1 + t} \,, $$ where $$ \alpha = -1 + \sum_{i \neq j} \lvert x_i \rvert \lvert x_j \rvert = -2 + \sum_{ij} \lvert x_i \rvert \lvert x_j \rvert = \lvert x \rvert_1^2 - 2 \,. $$ We can choose $x$ so that $\lvert x \rvert_1^2 = n$ and $n > 2$ by assumption. Such a choice yields $g$ that is not convex.

share|improve this answer
add comment

I'm going to share the work I did on this problem---even though I didn't get a positive result. Perhaps you can work with it.

We can write your problem as follows: $$f(A) = \inf \{ \|B\|_1 \,|\, B=A^{-1} \}$$ Now consider the following modified function: $$\tilde{f}(A) = \inf \{ \|B\|_1 \,|\, B\succeq A^{-1} \} = \inf\{ \|B\|_1 \,|\, B - A^{-1} \in \mathcal{S}^n_+ \}$$ This function is convex. Here's the proof. First, define the following extended-valued function: $$g(A,B) = \begin{cases} \|B\|_1 & A \succ 0, ~ B \succeq A^{-1} \\ +\infty & \text{otherwise} \end{cases}$$ If $g(A,B)$ is convex, then so must be $\tilde{f}$, since partial minimizations of convex functions are convex, and $\tilde{f}(A) = \inf_B g(A,B).$ Clearly, $g$ is convex at points in its domain---but we do not know if the domain is convex, yet: $$\mathop{\textrm{dom}}(g) = \{ (A,B)\in\mathcal{S}^n\times\mathcal{S}^n \,|\, A \succ 0, ~ B \succeq A^{-1} \} = \left\{ (A,B)\in\mathcal{S}^n\times\mathcal{S}^n \,\middle|\, A \succ 0, ~ \begin{bmatrix} B & I \\ I & A \end{bmatrix} \succeq 0 \right\}.$$ This is a convex set, being the intersection of some linear matrix inequalities on $(A,B)$. Therefore, $g$ is convex, and so is $\tilde{f}$.

Now: is $f\equiv \tilde{f}$? It is true for other convex functions on $B$, such as the trace and the determinant: and indeed, both $\mathop{\textrm{Tr}}(A^{-1})$ and $\mathop{\textrm{det}}(A^{-1})$ are convex. But is it true for $\|A^{-1}\|_1$? Before I tried to prove this, I wrote some MATLAB code using CVX, a toolbox I wrote for convex optimization. Here's the code:

function test_norm1inv( A )
n = size(A,1);
cvx_begin quiet
    variable B(n,n) symmetric
    minimize(sum(sum(abs(B))));
    [B,eye(n);eye(n),A] == semidefinite(2*n)
cvx_end
fprintf( 'CVX result: %g\n', cvx_optval )
fprintf( 'Analytic result: %g\n', sum(sum(abs(inv(A)))) );

Here's some example output:

>> A = randn(10,10); test_norm1inv( A*A' )
CVX result: 44998.8
Analytic result: 45000.3
>> A = randn(10,10); test_norm1inv( A*A' )
CVX result: 686.876
Analytic result: 686.889
>> A = randn(10,10); test_norm1inv( A*A' )
CVX result: 87.0088
Analytic result: 99.938
>> A = randn(10,10); test_norm1inv( A*A' )
CVX result: 82.3252
Analytic result: 96.8455

BZZT. I'm glad I didn't spend any time trying to prove the positive---it is clear that $\tilde{f}\not\equiv f$. I've manually confirmed that the matrix $B$ produced by CVX does indeed satisfy $B\succeq A^{-1}$, and that $\|B\|_1<\|A^{-1}\|_1$. Indeed, the values of $B$ produced by this approach look quite different from $A^{-1}$.

Now I have to say that this shakes any confidence I might have had that your original function, $f$, is convex. That said, I also wrote some simple code to perform convexity tests on pairs of randomly generated PSD matrices, and it failed to find a counterexample. If I think of anything more, I will edit my answer.

share|improve this answer
add comment

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.