Consider a matrix $A \in \mathbb{R}^{m \times n}$ where $n >> m$. In other words, $A$ has much more columns than rows. Also, consider we are given a fixed number (integer) $m \leq r < n$. I'm trying to find a matrix $B \in \mathbb{R}^{r \times m}$ such that $B' B = I_m$ (i.e., $B'$ is the left inverse of $B$) and $BA$ is very sparse, as much as possible.
My first idea was to consider the case $r = m$ and take the $QR$ factorization of $A$. Then set $B = Q^T$ to get $$BA = Q^TA = Q^TQR = I_mR = R,$$ a triangular (and rectangular) matrix. This matrix has a few zeros in the first $m$ columns, but since $m$ is much smaller than $n$, there are a lot of non zero terms left. Also, in my context usually $r$ will be bigger than $m$ and smaller than $n$, so I don't want to choose specif values for $r$. I really want a general approach that maximizes the number of zero entries in $BA$ for a generic $r$ between $m$ and $n$.
I wonder if there is a better matrix to do the job. Hope you can help me.
Thank you.
You can pose the following optimization problem: $$min_{C,B} \quad \|C\|_1 \qquad \text{s.t. } \quad C = BA.$$ An easy way to solve this problem is the ADMM approach. In summary, you add the augmented Lagrange multiplers:
$$L(C,B,\Delta) = \|C\|_1+\frac{\rho}{2}\|BA-C\|_F^2+Tr(\Delta^\top(BA-C)),$$ and alternatively update $C,B,\Delta$ until convergence.
The above approach is a general optimization framework and for generic values of $r$. But you need to choose $r$ beforehand, so I am not sure if it's applicable to your problem.