(This is for my graduate research -- not exactly homework)
Given an arbitrary $X \in \Re^{M_X \times N}, Y \in \Re^{M_Y \times N}$,
I want to find $A \in \Re^{K \times M_X}, B \in \Re^{K \times M_Y}$ such that $AX = BY \in \Re^{K \times N}$ and $\text{rank}(AX)=K \ll (M_X,M_Y) \le N $
I think this should be possible with $O(K)$ random sketches (I want this since $N$ may be huge and $X,Y$ may have fast/sparse implementations), but I'm stuck.
FWIW, The first order necessary conditions for $\min_{A,B} \|AX-BY\|_F$ are $(AX-BY)X^T=0^{K \times M_X}$ and $(AX-BY)Y^T=0^{K \times M_Y}$. Combined, $AX\begin{bmatrix}X\\Y\end{bmatrix}^T = BY\begin{bmatrix}X\\Y\end{bmatrix}^T$. This is not much more descriptive than the original $AX=BY$.