Consider a linear subspace $S$ of the space of $m\times n$ real valued matrices $\mathbb R^{m\times n}$.
When does $S$ admit a basis consisting only of rank-1 matrices?
I.e. is there a simple criterion or algorithm to check for the existence of such a basis?
Background:
I would also be interested in the case when we also allow diagonal, permutation, or generally sparse matrices. This is because the matrix vector product $A\cdot x$, which usually costs $O(n^2)$ to evaluate, can be computed in $O(n)$ for the aforementioned matrix types. Thus, if we have a subspace $S\le \mathbb R^{m\times n}$ with $\dim(S)\ll m\times n$ we can potentially achieve huge performance gains by representing parametrized matrices in $S$ using a basis which only consists of these "cheap" matrices.
Formulation as an optimization problem:
Given a finite set of $m\times n$ real-valued matrices $\mathcal A = \{A_1,\ldots, A_d\}\subset \mathbb R^{m\times n}$, find
$$ \min_{\mathcal B = \{B_1, \ldots, B_d\}\subset \mathbb R^{m\times n}} \sum_{i=1}^d \text{rank}(B_i) \qquad\text{s.t.}\quad\big\langle \mathcal A\big\rangle = \big\langle \mathcal B\big\rangle $$
Is there any hope of solving this problem exactly? If not, what types of optimization algorithms are suitable for this kind of problem, given that both the objective function and the constraint are discontinuous?
Example: given
$$S= \left\langle \underset{A_1}{\begin{bmatrix}4 & 5 & 6 \\ 7 & 9 & 11 \end{bmatrix}}, \underset{A_2}{\begin{bmatrix}2 & 3 & 4 \\ 5 & 7 & 9 \end{bmatrix}} \right\rangle $$
We can represent $S$ equivalently as
$$S= \left\langle \underset{B_1}{\begin{bmatrix}3 & 4 & 5 \\ 6 & 8 & 10 \end{bmatrix}}, \underset{B_2}{\begin{bmatrix}1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}} \right\rangle = \left\langle \underset{u_1v_1^T}{\begin{bmatrix} 1 \\ 2 \end{bmatrix}\begin{bmatrix}3 & 4 & 5\end{bmatrix}}, \underset{u_2v_2^T}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}\begin{bmatrix} 1 & 1 & 1\end{bmatrix}}\right\rangle $$
Because $A_1=u_1v_1^T + u_2v_2^T$ and $A_2 = u_1v_1^T - u_2v_2^T$.
Now consider a parametrized matrix $C$ in $S$. If we express $C$ in the basis $A$, i.e. $C = \lambda_1 A_1 + \lambda_2 A_2$, then computing the matrix vector product $C\cdot x$ will cost us at least 16/10 multiplications/additions, whereas if we represent it in the basis $B$, i.e. $C=\lambda_1 u_1v_1^T + \lambda_2 u_2v_2^T$, then the matrix-vector product $C\cdot x$ can be done in 12/8 multiplications/additions.
More generally, for a space of dimension $d$ the scaling is $O(dmn)$ for a dense basis and $O(d(m+n))$ for a rank-1 basis in terms of both elementary multiplications and additions. (using elementary matrix multiplication)
