Take the 2-minute tour ×

Given a matrix M, I want to find an orthogonal matrix U that maximizes the number of entries that are zero in the product MU. How do I go about doing this?

share|improve this question

1 Answer 1

As far as I know, the problem of finding the maximizer U will be a hard and probably intractable problem.

However, if you change your notion of sparsity, there are reasonable methods. These alternate notions of sparsity say that a matrix is sparse if it has many entries of small absolute value. To do a maximization problem, you have to cook up a function that measures the sparsity and hope that it lends itself to a tractable optimization problem.

One method that I have used is the Varimax algorithm (you can google it, there is a lot written about it). This method measures the sparsity of a matrix by computing the variance of the squares of the entries of matrix. If all of the entries are of similar size, this variance will be small. If many of the entries are of small absolute value, this variance will be large. So by maximizing this variance you maximize a reasonable notion of sparsity. The Varimax algorithm is a iterative method that finds a local maximum for this variance over the set of MU where U is othogonal.

There are other algorithms out there (Promax, Quartimax, etc, etc) which I have not used, but I gather are simple variations of the Varimax algorithm for a different objective function. In all these cases one is trying to find the maximally sparse rotation of the given matrix.

Finally, if the matrix M you input into these algorithms has a good reason to be sparse, it turns out in practice that many of the entries will actually end up being zero on the nose. So for many real-world applications this does a pretty good job.

These methods are all a small part of a large class of statistical techniques that go under the heading of "factor analysis". If you google factor analysis, you'll probably find a lot of useful stuff.

share|improve this answer

Your Answer


