2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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).

$\endgroup$

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.