0
$\begingroup$

Motivation: We wish to make an second order approximation of a nonconvex function $f(x), x \in \mathbb{R}^n$ such that it is convex, however we do not have guarantee that $\nabla^2 f(x)$ is convex

Given a matrix $A \in \mathbb{R}^{n \times n}$ not positive semidefinite

Does there exist a method to break $A$ that "preserves" $A$ as much as possible to obtain positive semidefinite matrix $M$ s.t. $A = M + N$?

If there is no method to tackle a general matrix, how about a symmetric matrix $A \in S^n$ where $S^n$ is the set of symmetric n by n real entries matrices?

$\endgroup$
  • $\begingroup$ You just need to remove negative eigenvalues of your matrix. $\endgroup$ – user85361 Nov 20 '15 at 13:26
1
$\begingroup$

In general, there is a decomposition of square matrices into a symmetric part and anti-symmetric part: $$A=M+N$$ where $M$ is symmetric and $N$ is anti-symmetric. This is a very general result, and this decomposition is in fact a Hilbert space decomposition so that $M$ is the "closest" symmetric matrix to $A$. It is easy to derive the forms of $M,N$: $$M=\frac{1}{2}(A+A^T), \ \mathrm{and} \ N=\frac{1}{2}(A-A^T).$$

A symmetric matrix $M$ then can be orthogonally diagonalized $M=Q^TDQ$, where the diagonal matrix $D=$ diag$(\lambda_1,...,\lambda_n)$ has real diagonal entries. Thus, we can write $D=D_{pos}+D_{neg}$, where $D_{pos}$ contains the positive eigenvalues and $D_{neg}$ the negative. Then we have $$A=Q^TD_{pos}Q+B$$ where obviously $Q^TD_{pos}Q$ is positive semi-definite and $B$ is everything else.

I'm unsure how much this matrix "preserves" $A$, as you say, but it is definitely the "positive semi-definite part of $A$"

$\endgroup$
  • $\begingroup$ This is useful, but our symmetric part may not be positive semidefinite $\endgroup$ – Carlos - the Mongoose - Danger Nov 20 '15 at 3:18
  • $\begingroup$ You are right, I have edited correspondingly $\endgroup$ – charlestoncrabb Nov 20 '15 at 3:34
  • $\begingroup$ With regards to the "preserving $A$" property, if $A$ itself is say negative semi-definite then the positive semi-definite part described will be zero... $\endgroup$ – charlestoncrabb Nov 20 '15 at 3:36

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.