On optimizing a function whose projection and projected vector go through a linear transformation Assume the two sets of vectors $\{\mathbf{a}_1,\ldots,\mathbf{a}_N\}$ and $\{\mathbf{b}_1,\ldots,\mathbf{b}_N\}$ of equal length. My goal is to find the optimum matrix $\mathbf{C}$ to the following optimization problem:
\begin{align}
 \max_{\mathbf{C}} \min_{i} \left|\operatorname{proj}_{\mathbf{C}\mathbf{a}_i}^\perp\mathbf{C}\mathbf{b}_i\right|^2.
\end{align}
Here, $\operatorname{proj}_{\mathbf{C}\mathbf{a}_i}^\perp$ is the projection operator on the subspace orthogonal to that spanned by $\mathbf{C}\mathbf{a}_i$, $\mathbf{C}$ is of fixed size, and some constraint on $\mathbf{C}$ must be imposed to avoid solutions that tend to infinite.
Even if a solution is not provided, partial solutions, approximations or reformulations of this problem are welcomed!
 A: Here is a classic solution based on the semidefinite relaxation of
a rank constraint. To begin, let us write $C\in\mathbb{R}^{r\times n}$.
Let $x_{i}=Ca_{i}$ and $y_{i}=Cb_{i}$. Then the maxi-min is equivalently
posed
$$
\text{maximize }t\text{ subject to }y_{i}^{T}y_{i}-\frac{y_{i}^{T}x_{i}x_{i}^{T}y_{i}}{x_{i}^{T}x_{i}}\ge t\text{ for all }i
$$
Suppose we introduce the semidefinite matrix decision variable $Z=C^{T}C\succeq0$
and imposed that $\mathrm{rank}(Z)\le r$. Then a valid, although
possibly nonunique choice of $C$ can always be recovered from $Z$
using the Cholesky factorization.
Now, the following is obvious from the cyclic property of trace
\begin{align} 
\alpha_{i} & =y_{i}^{T}y_{i}=\mathrm{Tr}\, Zb_{i}b_{i}^{T}\\
\beta_{i} & =x_{i}^{T}y_{i}=\frac{1}{2}\mathrm{Tr}\, Z(a_{i}b_{i}^{T}+b_{i}a_{i}^{T})\\
\gamma_{i} & =x_{i}^{T}x_{i}=\mathrm{Tr}\, Za_{i}a_{i}^{T}
\end{align}
all of which are linear constraints with respect to $Z$. Finally,
the following is obvious from the Schur complement lemma 
\begin{equation}
y_{i}^{T}y_{i}-\frac{y_{i}^{T}x_{i}x_{i}^{T}y_{i}}{x_{i}^{T}x_{i}}\ge t\iff\begin{bmatrix}\alpha_{i}-t & \beta_{i}\\
\beta_{i} & \gamma_{i}
\end{bmatrix}\succeq0.
\end{equation}
Combined, the nonconvex problem is
$$
\text{maximize }t\text{ subject to constraints for all }i,\,Z\succeq0,\,\mathrm{rank}(Z)\le r.
$$
Dropping the rank constraint yields the classic semidefinite relaxation, which is a convex problem you can readily solve using e.g. cvx or YALMIP.
If the relaxed solution satisfies $\mathrm{rank}(Z)\le r$, then we
are done, and a solution for $C$ is recovered by taking the Cholesky
factorization. If $\mathrm{rank}(Z)>r$ then there are a bunch of
standard techniques to force the solution rank to go down. For example,
we can modify the objective by $t-\eta\mathrm{Tr}\, Z$, where $\eta>0$
is a small constant introduced to promote low-rank solutions via the
trace penalty.
