Matrix Approximation with outer difference

Question

Given a skew-symmetric matrix $A$ what is the best approximation by an outer difference of a vector. Approximation norm could be either Frobenius or Euclidean.

The outer difference $D$ of vector $v$ is given by $$D_{ij} = v_i -v_j$$.

Answer 1

Using Frobenius norm and assuming real matrices. Let $e$ be a column vector of ones of the same length $n$ as $v$. The outer difference can be written as $v e^T - e v^T$. $$ ||A - (v e^T - e v^T)||^2_F = ||A||^2_F - 2 \langle A, v e^T - e v^T \rangle_{HS} + ||v e^T - e v^T||^2_F = ||A||^2_F - 2 \langle A, v e^T\rangle_{HS} + 2 \langle A, e v^T \rangle_{HS} + ||v e^T||^2_F - 2 \langle v e^T, e v^T \rangle_{HS} + ||e v^T||^2_F. $$ Substituting

• $\langle A, ve^T\rangle_{HS} = \mathrm{Tr}\, A^T v e^T = \mathrm{Tr}\, e^T A^T v = \mathrm{Tr}\, (A e)^T v = \langle Ae, v \rangle$,
• $\langle A, e v^T \rangle_{HS} = \mathrm{Tr}\, A^T e v^T = \mathrm{Tr}\, v e^T A = \mathrm{Tr}\, e^T A v = \mathrm{Tr}\, (A^T e)^T v = \langle A^T e, v\rangle = - \langle A e, v\rangle$,
• $||v e^T||^2_F = \mathrm{Tr}\, e v^T v e^T = ||v||^2 \mathrm{Tr}\, e e^T = n ||v||^2$,
• $\langle v e^T, e v^T \rangle_{HS} = \mathrm{Tr}\, e v^T e v^T = \mathrm{Tr}\, v^T e v^T e = \langle v, e\rangle^2$,
• $||e v^T||^2_F = n ||v||^2$,

in the above expression, $$ ||A - (v e^T - e v^T)||^2_F = ||A||^2_F - 4 \langle A e, v\rangle + 2 n ||v||^2 - 2 \langle v, e \rangle^2. $$ Its derivative w.r.t. $v$ is $-4 A e + 4 n v - 4 \langle v, e\rangle e = 4 (n I - e e^T) v - 4 A e$. Thus, solutions of $(n I - e e^T) v = A e$ are best approximations in Frobenius norm (since $0$ is always an eigenvalue of $(n I - e e^T)$, there may be more than one solution).