# Nearest Semi Orthonormal Matrix Using the Entry Wise ${\ell}_{1}$ Norm

Given an $m \times n$ matrix $M$ ($m \geq n$), the nearest semi-orthonormal matrix problem in $m \times n$ matrix $R$ is

$$\begin{array}{ll} \text{minimize} & \| M - R \|_F\\ \text{subject to} & R^T R = I_n\end{array}$$

A solution can be found by using Lagrangian or polar decomposition, and is known to be

$$\hat{R} := M(M^TM)^{-1/2}$$

If $\|\cdot\|_F$ is replaced by the entry-wise $1$-norm

$$\|A\|_1 := \|\operatorname{vec}(A)\|_1 = \sum_{i,j} |A_{i,j}|$$

the problem becomes

$$\boxed{\begin{array}{ll} \text{minimize} & \| M - R \|_1\\ \text{subject to} & R^T R = I_n\end{array}}$$

What do we know about the solutions in this case? Is $\hat{R}$ still a solution? If the solution is something else, do analytic forms or approximations exist? Any insight or direction to literature is appreciated.

We have the following non-convex optimization problem in (non-fat) $\mathrm X \in \mathbb R^{m \times n}$

\begin{array}{ll} \text{minimize} & \| \mathrm X - \mathrm A \|_1\\ \text{subject to} & \mathrm X^\top \mathrm X = \mathrm I_n\end{array}

where (non-fat) $\mathrm A \in \mathbb R^{m \times n}$ is given. The feasible region, defined by $\mathrm X^\top \mathrm X = \mathrm I_n$, is a Stiefel manifold whose convex hull is defined by $\mathrm X^\top \mathrm X \preceq \mathrm I_n$, or, equivalently, by the inequality $\| \mathrm X \|_2 \leq 1$. Hence, a convex relaxation of the original optimization problem is

$$\boxed{\qquad \begin{array}{ll} \text{minimize} & \| \mathrm X - \mathrm A \|_1\\ \text{subject to} & \| \mathrm X \|_2 \leq 1\end{array} \qquad}$$

Via the Schur complement test for positive semidefiniteness, $\mathrm X^\top \mathrm X \preceq \mathrm I_n$ can be rewritten as the following linear matrix inequality (LMI)

$$\begin{bmatrix} \mathrm I_m & \mathrm X\\ \mathrm X^\top & \mathrm I_n\end{bmatrix} \succeq \mathrm O_{m+n}$$

and, thus,

$$\begin{array}{ll} \text{minimize} & \| \mathrm X - \mathrm A \|_1\\ \text{subject to} & \begin{bmatrix} \mathrm I_m & \mathrm X\\ \mathrm X^\top & \mathrm I_n\end{bmatrix} \succeq \mathrm O_{m+n}\end{array}$$

Introducing variable $\mathrm Y \in \mathbb R^{m \times n}$, we obtain the following semidefinite program in $\mathrm X, \mathrm Y \in \mathbb R^{m \times n}$

$$\begin{array}{ll} \text{minimize} & \langle 1_m 1_n^\top, \mathrm Y \rangle\\ \text{subject to} & - \mathrm Y \leq \mathrm X - \mathrm A \leq \mathrm Y\\ & \begin{bmatrix} \mathrm I_m & \mathrm X\\ \mathrm X^\top & \mathrm I_n\end{bmatrix} \succeq \mathrm O_{m+n}\end{array}$$

### Numerical experiments

The following Python + NumPy + CVXPY code solves the convex relaxation of the original problem:

from cvxpy import *
import numpy as np

(m,n) = (30,3)

A = np.random.rand(m,n)

X = Variable(m,n)

# define optimization problem
prob = Problem( Minimize(norm(X-A,1)), [ norm(X,2) <= 1 ])

# solve optimization problem
print prob.solve()
print prob.status

# print results
print "X = \n", X.value
print "Spectral norm of X = ", np.linalg.norm(X.value,2)
print "X.T * X = \n", (X.value).T * (X.value)
print "Round(X.T * X) = \n", np.round((X.value).T * (X.value), 3)

Unfortunately, it produces

X.T * X =
[[ 0.50912521  0.22478268  0.25341844]
[ 0.22478268  0.4961892   0.2654229 ]
[ 0.25341844  0.2654229   0.46896397]]

which is quite "far" from the $3 \times 3$ identity matrix. This is disappointing.

However, using the Frobenius norm instead of the entry-wise $1$-norm:

prob = Problem( Minimize(norm(X-A,'fro')), [ norm(X,2) <= 1 ])

we obtain the following output

3.85187827124
optimal
X =
[[ 0.13146134 -0.14000011  0.32874275]
[-0.01234834  0.11837379  0.06604536]
[-0.10490978  0.10542352  0.25211362]
[ 0.25263062  0.14707194  0.03884215]
[ 0.00181182  0.4702248  -0.20126385]
[ 0.13013444 -0.07199484  0.08727077]
[ 0.19077548 -0.01423872 -0.05960523]
[ 0.2865637  -0.00202074  0.02844798]
[ 0.01602302  0.04395754  0.00154713]
[ 0.17932924  0.30926775 -0.05940074]
[ 0.42908676 -0.21953956  0.12394825]
[ 0.1255695   0.16415755  0.14634119]
[ 0.28144817  0.08592836  0.08426443]
[ 0.18209884  0.25983065 -0.02550957]
[ 0.11077068 -0.10874038  0.23649308]
[ 0.01565326  0.14043185  0.01186364]
[-0.04374642  0.20360714  0.01079417]
[-0.00440237  0.17746665  0.12931808]
[ 0.18899948  0.08389032  0.23493301]
[ 0.25802202  0.16171055  0.09263858]
[-0.01921053  0.26863496  0.13077382]
[-0.11175044  0.06137184  0.32758781]
[-0.20321302  0.37803842  0.17629377]
[-0.09301606 -0.0783033   0.36603431]
[-0.00572361  0.17620931 -0.04822991]
[ 0.24944001  0.18830197 -0.05522287]
[-0.2049578   0.1091767   0.38943593]
[ 0.36823908 -0.10026829  0.04425441]
[ 0.03582131  0.03531081  0.08337656]
[-0.07315648 -0.0739467   0.35741916]]
Spectral norm of X =  1.00018499995
X.T * X =
[[ 0.99843209 -0.00168429 -0.0019862 ]
[-0.00168429  0.99833293 -0.00222193]
[-0.0019862  -0.00222193  0.99790575]]
Round(X.T * X) =
[[ 0.998 -0.002 -0.002]
[-0.002  0.998 -0.002]
[-0.002 -0.002  0.998]]

where $\rm X^\top X$ is now quite "close" to the $3 \times 3$ identity matrix.

I did perform many numerical experiments, with several values for $m$ and $n$. My conclusions:

• Minimizing the Frobenius norm worked rather satisfactorily for very tall matrices ($m \gg n$).

• Unfortunately, minimizing the entry-wise $1$-norm failed in all experiments I performed.

By "worked" and "failed" I mean that the solution of the relaxed convex problem is a solution of the original (non-convex) optimization problem or not, respectively.

• Your notation is inconsistent with the original question. Your $A$ is the original poster's $M$. – Brian Borchers Apr 5 '18 at 1:13
• My comment was merely there to help any reader who was confused by change in notation. – Brian Borchers Apr 5 '18 at 1:17
• I'm with Brian on this one—the notation change is unnecessarily distracting. As for using $m$ and $M$ at the same time, well, that would throw me off every time I need to formulate a big-$M$ method! ;-) – Michael Grant Apr 5 '18 at 1:17
• $$\begin{array}{ll} \text{minimize} & \langle 1_m 1_n^\top, \mathrm Y \rangle\\ \text{subject to} & - \mathrm Y \leq \mathrm R - \mathrm M \leq \mathrm Y\\ & \begin{bmatrix} \mathrm I_m & \mathrm R\\ \mathrm R^\top & \mathrm I_n\end{bmatrix} \succeq \mathrm O_{m+n}\end{array}$$ – Rodrigo de Azevedo Apr 5 '18 at 1:25
• @RodrigodeAzevedo, Is there a projection onto the Stiefel Manifold (Also the space of Semi Orthogonal Matrices)? – Royi Feb 3 '19 at 4:29