Parametrising a sparse orthogonal matrix

Question

I need to find a way to parametrise a matrix that is both sparse (to some degree) and orthogonal, i.e., I am looking for a parametrisation that describes $A \in \mathbb{R}^{n\times m}$ such that $AA^𝑇=𝐼$ and $||A||_0 << nm$.

It is not hard to generate orthogonal matrices through an SVD, but the orthogonal components of a sparse matrix are not guaranteed to be sparse themselves. Similarly, priors like spike and slab can lead to sparse matrices, but those are usually non-orthogonal.

Thus, is anyone aware of any work that presents a way of generating matrices that are both sparse and orthogonal?

Answer 1

The smallest number of nonzero entries in an $n\times n$ fully indecomposable$^*$ orthogonal matrix is $4n−4$. A method to construct such a matrix is described in Sparse orthogonal matrices (2003).

$^*$ A fully indecomposable matrix does not have a $p\times q$ zero submatrix with $p+q=n$.

Answer 2

The four-argument version of Matlab's sprand can generate a sparse orthogonal matrix, with suitable arguments. According to the documentation,

[the matrix] is generated by random plane rotations applied to a diagonal matrix with the given singular values. It has a great deal of topological and algebraic structure.

From this brief description, I infer that it is generated by taking a random diagonal matrix with $\pm 1$ on the diagonal and applying a few Givens rotations with random $i,j,\theta$ to it (either to the left or to the right, randomly again).