4
$\begingroup$

Suppose we have two symmetric positive semidefinite $n$ dimensional matrices $A$ and $B$. We use the notation $X\leq Y$ means that $Y-X$ is positive semidefinite.

Suppose $A \not\leq B$ i.e. $B-A$ has at least one negative eigenvalue. We are interested in perturbing $A$ to some positive semidefinite $\tilde{A}$ such that $\tilde{A} \leq B$ while minimizing $|A-\tilde{A}|_1$ where $|\cdot|_1$ is the nuclear norm and defined by

$$|X|_1 := \text{Tr} \left( \sqrt{X^\dagger X} \right)$$

and $X^\dagger$ is the transpose conjugate of $X$.

To make things simpler, I will now consider the case where $A$ is a rank-$1$ matrix. Is it true that

$$\tilde{A} = \lambda A$$

for some $\lambda < 1$? An immediate corollary is that $\tilde{A}\leq A$.


EDIT: After a bit of searching, I found a result for the same question but where the norm considered is the induced 2-norm (spectral norm) or the Frobenius norm.

For the induced 2-norm (spectral norm), it holds that $\tilde{A} = A - \lambda I$ where $\lambda$ is the smallest positive number such that $\tilde{A}\leq B$ is true. So for this case, my conjecture that $\tilde{A} = \lambda A$ is false but the statement $\tilde{A}\leq A$ is true.

For the Frobenius norm case, we first write the polar decomposition of $B-A = UH$. Then $B -\tilde{A} = \frac{1}{2}(B - A + H)$ is the solution. Since $H= ((B-A)^\dagger(B-A))^{1/2}\geq B-A$, one can again conclude that $\tilde{A}\leq A$

I do not know what happens for the 1-norm though.


EDIT 2: Here is another look at the problem that almost works. Suppose the solution $\tilde{A}\not\leq A$. We prove that there exists some $A'$ such that $A'\leq B, A'\leq A$ and $|A'-A|_1\leq|\tilde{A}-A|_1$.

Let us diagonalize $\tilde{A}-A = ZDZ^\dagger = ZD^{+}Z^\dagger + ZD^{-}Z^\dagger$ where $D$ is diagonal, $D^{\pm}$ is also diagonal and includes the nonnegative and negative eigenvalues respectively. By assumption $\tilde{A}\leq B \implies A + ZD^{+}Z^\dagger + ZD^{-}Z^\dagger \leq B$. Define $A':= A + ZD^{-}Z^\dagger$.

Since $ZD^{+}Z^\dagger$ is positive semidefinite, it holds that $A' = A + ZD^{-}Z^\dagger \leq B$.

Since $ZD^{-}Z^\dagger$ is negative definite, it follows that $A'\leq A$.

Finally, $|A' - A|_1 = |ZD^{-}Z^\dagger|_1 = |D^{-}|_1 \leq |D^{+}+D^{-}|_1 = |Z(D^{+}+D^{-})Z^\dagger|_1 = |\tilde{A} - A|_1$

EDIT 3 Unfortunately, the $A'$ constructed is not positive semidefinite in general.

$\endgroup$
4
  • 2
    $\begingroup$ You might be able to formulate the problem as a semidefinite program $\endgroup$ – Ben Grossmann Jun 27 '20 at 23:25
  • $\begingroup$ @Omnomnomnom I edited the question with an attempted proof. If you could have a look, I'd be very grateful! $\endgroup$ – user1936752 Jul 1 '20 at 14:37
  • 1
    $\begingroup$ I don't see any issues with your proof, it seems as though you're right! $\endgroup$ – Ben Grossmann Jul 1 '20 at 15:13
  • $\begingroup$ Thank you very much! $\endgroup$ – user1936752 Jul 1 '20 at 15:17
1
+50
$\begingroup$

Some thoughts on the problem:

As a further simplification, I suggest that we say that $\tilde A$ does not only satisfy $\tilde A \leq B$, but also has a rank of $1$. If your hypothesis is correct, then this assumption should not change our answer. Write $$ A = \alpha xx^T, \quad \tilde A = \beta yy^T $$ for some scalars $\alpha, \beta > 0$ and unit vectors $x,y$. The minimization problem now becomes $$ \min_{y \in \Bbb R^n, \beta > 0} |\alpha xx^T - \beta yy^T|_1 \quad \text{s.t.} \quad \beta yy^T \leq B. $$ Now, I make several claims:

  1. $yy^T \leq B \iff \beta \leq [y^TB^+y]^{-1}$ where $B^+$ denotes the Moore-Penrose pseudoinverse of $B$. I give some proofs of this here.

  2. $\alpha xx^T - \beta yy^T$ has the same nuclear norm as that of the $2 \times 2$ matrix $\pmatrix{\alpha & \alpha (x^Ty)\\ -\beta (x^Ty) & -\beta}$. (explanation below).

  3. The nuclear norm turns out to be $|M|_1 = \sqrt{(\beta - \alpha)^2 + 4(1 - (x^Ty)^2)}$.

My first approach would be to, by considering the nuclear norm as a function of $\beta$, maximize the nuclear norm given a particular choice of $y$.


The nuclear norm of a symmetric matrix is the sum of the absolute values of its eigenvalues. With that said, we want the eigenvalues of $M = \alpha xx^T - \beta yy^T$.

$$ M = \pmatrix{x & y} \pmatrix{\alpha & 0 \\ 0 & -\beta} \pmatrix{x & y}^T. $$ Because $AB,BA$ have the same non-zero eigenvalues, $M$ will have the same non-zero eigenvalues as the $2 \times 2$ matrix $$ N = \pmatrix{\alpha & 0 \\ 0 & -\beta} \pmatrix{x & y}^T\pmatrix{x & y} = \pmatrix{\alpha x^Tx & \alpha x^Ty\\ -\beta x^Ty & -\beta y^Ty}. $$

Point 3: $$ \lambda^2 + (\beta - \alpha) \lambda + ((x^Ty)^2 - 1)\alpha\beta \implies\\ \lambda = \frac{\alpha - \beta \pm \sqrt{(\beta - \alpha)^2 + 4(1 - (x^Ty)^2)}}{2} $$

$\endgroup$
4
  • $\begingroup$ Great answer, thank you! It seems you've solved the problem, unless I am missing something? We want to minimize $|M|_1$ and regardless of $\alpha$ or $\beta$, this holds when $x^Ty$ is maximized. $x = y$ is therefore true. $\endgroup$ – user1936752 Jun 27 '20 at 21:42
  • 1
    $\begingroup$ @user1936752 It's not that simple. Note that how large we can make $\beta$ without failing the $\tilde A \leq B$ condition depends on our particular choice of $y$. $\endgroup$ – Ben Grossmann Jun 27 '20 at 21:44
  • 1
    $\begingroup$ @user1936752 So it could be that the $\tilde A \leq B$ condition forces $(\beta - \alpha)^2$ to be large in the case that $y = x$. $\endgroup$ – Ben Grossmann Jun 27 '20 at 21:48
  • $\begingroup$ I see your point. But it's a very elegant perspective on the problem - thank you for this! $\endgroup$ – user1936752 Jun 27 '20 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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