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?


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)

  • $\begingroup$ Am I missing something, or why is the set of matrices of one $1$ and the rest zero not always a basis? $\endgroup$
    – Toffomat
    Jun 14 at 10:59
  • $\begingroup$ @Toffomat I added an example to clarify the problem. $\endgroup$
    – Hyperplane
    Jun 14 at 11:17
  • $\begingroup$ I think I solved the problem in the special case where $m,n \le 2$. Is this worth an answer? $\endgroup$ Jun 18 at 14:12
  • $\begingroup$ @MorganRodgers The $2 \times 2$ case is still interesting in my opinion. There the property boils down for the subspace to be positive or negative definite. $\endgroup$ Jun 18 at 14:30

I assume by "simple" you mean computationally efficient. It is unlikely that efficient algorithm for determining the existence of such a basis.

The sparse basis case is basically equivalent to the "matrix sparsification" problem. It is NP-hard to even approximate the sparsest basis for a linear space (see https://citeseerx.ist.psu.edu/viewdoc/download?doi= So under the widely believed assumption that P$\neq$NP, there is no efficient algorithm for the case of sparse matrices.

The problem of finding a low-rank basis can easily be seen as generalizing the sparse basis problem, by embed the vector space into the space of diagonal matrices. A sparse basis corrsponds to a basis of sparse diagonal matrices, which has low rank. Therefore, the low-rank case is also NP-hard.

As far as I know, the case where you are promised that there is a rank-1 basis has not been proven hard, but has also not been proven easy. This specific problem was mentioned here: https://link.springer.com/content/pdf/10.1007/s10107-016-1042-2.pdf. It seems very unlikely that the rank-1 case would turn out to be easy, given that the problem in general is hard.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.