How to enforce a matrix of unknowns to be a sparse block diagonal matrix?

1

Currently, I am minimizing the quadratic objective \|\mathbf{A}\mathbf{X}\mathbf{B}\mathbf{d} -\mathbf{c} \|^2 as follows

echo on
cvx_begin
    variable xx(num_triangles*3,num_triangles*3)
    minimize( norm( A * xx * B * d - c ) )
cvx_end
echo off

However, \mathbf{X} is a very large matrix (about 50,000 \times 50,000, which is too big). Good news is that \mathbf{X} is a block diagonal matrix (of 3 \times 3 transformation matrices) and, therefore, it is highly sparse.

To give an example, for \mathbf{X} \in \mathbb{R}^{9 \times 9} I would be looking for such matrix.

|  X1  X4  X7   0   0   0   0   0   0 |
|  X2  X5  X8   0   0   0   0   0   0 |
|  X3  X6  X9   0   0   0   0   0   0 |
|   0   0   0 X10 x13 x16   0   0   0 |
|   0   0   0 X11 x14 x17   0   0   0 |
|   0   0   0 X12 x15 x18   0   0   0 |
|   0   0   0   0   0   0 X19 x22 x25 |
|   0   0   0   0   0   0 X20 x23 x26 |
|   0   0   0   0   0   0 X21 x24 x27 |

so in fact I am only solving for 27 variables, not 9 \times 9 = 81. And this scales pretty badly.

But I don’t know how I can enforce such structure when formulating the minimization problem. If I declare a normal square matrix of the size I need, the memory just explodes. Any ideas on how to reformulate the problem in a way that I actually solve for the number of unknowns?

Disclamer: I actually asked the same in Mathematics Stackoverflow, but I thought there may be a CVX specific solution for my problem hence I replicate it here.

2

I don’t know how well this would work, but how about declaring a bunch of 3 by 3 matrix variables, or perhaps a single 3 by 3 by num_triangles, and then construct X out of this using blkdiag or other MATLAB concatenation methods? It is “legal” in CVX and will enforce zeros in the off-block diagonal elements, but i don’t know how well it will work from a memory or performance perspective. I leave it to you to work out the details and experiment within this framework. Please report your findings.