Finding the closest matrix of a given form

Question

Let's say I have a vector $(a_1\dots a_n)$, where each component is between $-1$ and $1$. Now from this vector I define a $n\times n$ matrix $M$ such that

$$M_{ij} = \begin{cases} 1&\,& i = j\\ a_i\cdot a_j&\,& i\neq j\end{cases}$$

I now call $E$ the space of all matrices $M$ I can build with that process.

Now, I have a given matrix $A$ that can be assumed to be symetrical, having $1$ on the diagonal and that is symetric definitive positive.

Is there a way to find a matrix from the space $E$ that is the closest to $A$? By "closest" I mean with any norm that seems reasonable.

I guess this can be difficult to solve, and I'm just trying to find direction for this problem. Alternatively, any iterative solution that can converge to the result could be fine as well.

Any idea? Thanks!

Answer 1

So, you can write any matrix in $E$ as

$$ M = I + \underline{a}\underline{a}^T - \sum_{k=1}^{n} \underline{e}_k\underline{e}_k^Ta_k^2 $$

where $\underline{a}$ is a vector with components in $[-1,1]$. If you use the $2$-norm it's going to be complicated, I think, cause you will need to solve a min-max problem. $1$-norm and $\infty$-norm don't look much easier. But perhaps with the Frobenius norm: given a matrix $B=(b_{ij})$, find $\underline{a}$ that solves

$$ \arg\min \sum_{i,j} \left(\delta_{ij} + a_ia_j - \delta_{ij}a_ia_j - b_{ij}\right)^2\\ \mbox{subject to } -1\leq a_k \leq 1, k = 1,\ldots,n $$

This is a (bi)-quadratic optimization problem in $\mathbb{R}^n$, with inequality constraint. I bet there is some literature about such problems. I'm not sure this is convex. But it looks like, in which case you could use barrier penalization and then use some newton-like method.

Answer 2

This is a convex relaxation approach based on the answer by user bartgol. Let $B=A-I$ ($I$ is identity). Also, for any matrix $X$, let $diag(X)$ denote a diagonal matrix whose diagonal entries are same as that of $X$. Then, I can rewrite your problem as \begin{align} \min_{X} &\mid\mid B-X-diag(X)\mid\mid_{frob} && (\mbox{find an X minimizing the given frobenius norm})\\ such.that.~~~&X\geq 0 && (\mbox{X should be positive semi-definite}) \\ &rank(X)\,=\,1 && (\mbox{rank of X should be one}) \\ &X_{i,i} \leq 1,~\forall i && (\mbox{all diagonal entries should be less than 1}) \end{align} The idea is as follows, the first two constraints implies that $X$ should be of the form $X=aa^T$ for some vector $a$.(verify yourself). Thus $X_{i,i}=a_i^2$(verify). Thus the last constraint implies that $a_i^2\leq 1$ which is same as $a_i\in [-1,1]$ .

Now comes the amazing part. The objective function is convex, all constraints are convex except the rank constraint. Thus, you simply the drop non-convex rank constraint and make it convex. This belongs to the class of semi-definite programs and then can be solved using an SDP solver. Yes, you may not get a rank-one solution. But then you can get a high quality sub-optimal solution using several well known techniques in optimization literature. For instance, randomization is a well known strategy. Search about semi-definite relaxation to learn more about this kind of theory.

PS: If you are familiar with MATLAB, you can use the package well-known as CVX to solve this. I simulated your problem for some random examples and it does give rank-one solutions for most of the cases. The problem will look like this in CVX modelling language

cvx_begin sdp 
variable X(N,N) symmetric
minimize norm(B-X-diag(diag(X)),'fro')
X>=0
diag(X) <= 1
cvx_end

(yes, only that five lines of code is needed!!).