Matrix decompositions with sparsity constraints

Suppose we are given a finite square matrix $A \in \mathbb{R}^{n \times n}$ . We would like to factorize $A$ into $N$ (where $N$ is finite) matrices

$A = W_{N-1} W_{N-2} \ldots W_ {2} W_{1} W_{0}$ ,

where factors $W_0, W_1, \ldots, W_{N-1} \in \mathbb{R}^{n \times n}$ are required to have a certain sparsity pattern, i.e., a subset of their $n^2$ entries must be zero.

Definition: Let $\mathcal{I}_n = \{1, 2, \ldots, n\}$ and $\mathcal{I}_n^2 = \mathcal{I}_n \times \mathcal{I}_n$ . A sparsity pattern $\mathcal{S}_n$ is a set of ordered pairs $(i,j) \in \mathcal{I}_n^2$ that indicate which entries of a $n \times n$ matrix are constrained to be zero.

Note that $\mathcal{S}_n \subseteq \mathcal{I}_n^2$ . If there are no sparsity constraints, then $\mathcal{S}_n$ is an empty set. Set $\mathcal{I}_n^2 \setminus \mathcal{S}_n$ contains the indices of the entries of a $n \times n$ matrix which are unconstrained, i.e., “free”.

__________

Problem: Given a matrix $A \in \mathbb{R}^{n \times n}$ and a particular sparsity pattern $\mathcal{S}_n$ , how can we find if it is possible to factorize $A$ into $N$ factor matrices (where $N$ is finite) whose sparsity pattern is the specified one? If such factorization is possible, how can we compute each factor $W_1, W_2, \ldots, W_{N-1}$ and $N$ ?

__________

This problem is easy to pose, but I have found it very hard to attack. I have tried various approaches… and none worked. Does anyone have any ideas?

__________

Example: suppose we are given a $5 \times 5$ real matrix

$A = \left[\begin{array}{ccccc} 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ \end{array}\right]$ .

We would like to factorize matrix $A$ into $N$ factors $\{W_k\}_{k =0}^{N-1} \in \mathbb{R}^{5 \times 5}$ whose sparsity pattern is represented pictorially by

$\left[\begin{array}{ccccc} \times & \times & 0 & 0 & 0\\ \times & \times & \times & 0 & 0\\ 0 & \times & \times & \times & 0\\ 0 & 0 & \times & \times & \times\\ 0 & 0 & 0 & \times & \times\\\end{array}\right]$ ,

where a “ $\times$ ” in the $(i,j)$ entry means that the $(i,j)$ entry is unconstrained, i.e., it is allowed to take any value in $\mathbb{R}$ . If you are familiar with numerical PDE’s, you certainly encountered matrices with this sparsity pattern when solving diffusion or wave equations in one spatial dimension using finite difference methods.

__________

Even though this example seems fairly “simple” (it’s only a $5 \times 5$ matrix after all!), I have not yet found an approach that works.

Like this:

Be the first to like this post.

Tags: Mathematics, Matrix Decompositions, Matrix Theory, Sparsity

This entry was posted on December 12, 2008 at 23:39 and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

11 Responses to “Matrix decompositions with sparsity constraints”

Rod Carvalho Says:
December 13, 2008 at 13:31 | Reply
Note that the constraint that $N$ must be finite is critical.

For example, the $A$ matrix in the example above

$A = \left[\begin{array}{ccccc} 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ \end{array}\right]$

can easily be factored into an infinite number of matrices with the specified sparsity pattern. Consider the following $5 \times 5$ symmetric, non-negative matrix

$C = \frac{1}{2} \left[\begin{array}{ccccc} 1 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 1\\\end{array}\right]$ .

Let $\mathbf{1}_5 \in \mathbb{R}^5$ be a column vector whose all five entries are ones. Note that $C \mathbf{1}_5 = \mathbf{1}_5$ and therefore we can conclude that $\mathbf{1}_5$ is a right eigenvector of matrix $C$ , and that its corresponding eigenvalue is $1$ . It can be shown that $C$ has spectral radius $\rho(C) = 1$ . Since $C$ is real and symmetric, we have that its eigenvalues are real. Therefore, the largest eigenvalue in absolute value is $\lambda_1 = 1$ , whose corresponding (normalized) eigenvector is $q_1 = \left(\frac{1}{\sqrt{5}}\right) \mathbf{1}_5$ . Since the algebraic multiplicity of $\lambda_1$ is $1$ , the Jordan block associated with $\lambda_1$ is $1 \times 1$ and therefore the limit $\lim_{k \rightarrow \infty} C^k$ should be finite

$\displaystyle\lim_{k \rightarrow \infty} C^k = q_1 q_1^T = \frac{1}{5} A$ ,

thus, we could choose factor matrices $W_0 = 5 I_5$ , $W_k = C$ for all $k \geq 1$ , such that

$A = 5 \underbrace{C C C C C C \ldots C C C}_{\text{infinite number of factors}}$ .

We have have thus factored $A$ into an infinite number of factor matrices with the specified sparsity pattern. However, this is not what we are after. We want $N$ to be finite.
Sune Kristian Jakobsen Says:
December 14, 2008 at 21:24 | Reply
Your example can be factored:

$W_3 = \begin{pmatrix} 0 &1 &0 &0 & 0\\ 0 & 1 & 0 & 0& 0\\ 0 & 0& 1& 0& 0\\ 0 & 0& 0& 1& 0\\ 0& 0& 0& 1& 0 \end{pmatrix}$

$W_2 = \begin{pmatrix} 0 & 0& 0& 0& 0\\ 0 &0 & 1 & 0& 0\\ 0 & 0 & 1 & 0& 0\\ 0 &0 &1 & 0 &0\\ 0 &0 & 0 & 0 & 0 \end{pmatrix}$

$W_1 = \begin{pmatrix} 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}$

$W_0 = \begin{pmatrix} 0 & 0 & 0 &0 & 0\\ 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}$

It is easy to generalize to bigger matrices, but I don’t know how to solve the general problem of factoring a general matrix into matrices with a given sparsity pattern.

Rod Carvalho Says:
December 14, 2008 at 22:40 | Reply

Sune,

Tak!! I appreciate you took the time to write a solution. MATLAB says you’re right!

W_3 = [0 1 0 0 0; 0 1 0 0 0; 0 0 1 0 0; 0 0 0 1 0; 0 0 0 1 0];
W_2 = [0 0 0 0 0; 0 0 1 0 0; 0 0 1 0 0; 0 0 1 0 0; 0 0 0 0 0];
W_1 = [0 0 0 0 0; 0 0 0 0 0; 0 1 1 1 0; 0 0 0 0 0; 0 0 0 0 0];
W_0 = [0 0 0 0 0; 1 1 0 0 0; 0 0 1 0 0; 0 0 0 1 1; 0 0 0 0 0];
disp(' W_3 W_2 W_1 W_0 = '); 
disp(W_3 * W_2 * W_1 * W_0);

Would you mind sharing how you got to this solution?

Sune Kristian Jakobsen Says:
December 15, 2008 at 00:15 | Reply
Det var så lidt!

I used some trial & error to find the example, but I understand why it works: If you multiply $W_2$ and $W_1$ you will get:

$\begin{pmatrix} 0 & 0 & 0 & 0& 0\\ 0 & 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1& 0\\ 0 & 1& 1& 1& 0\\ 0 & 0& 0& 0& 0\end{pmatrix}$

If you multiply a matrix by $W_3$ from the left, it will simply copy the 2nd row to the first, and the 4th to the 5th. So

$W_3 W_2 W_1= \begin{pmatrix} 0 & 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 & 0\\ 0 & 1 & 1& 1 & 0\\ 0 & 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 & 0 \end{pmatrix}$

Similarly, if you multiply a matrix from the right by $W_0$ , it will copy the 2nd column to the first and the 4th to the 5th.

If you want to solve the similar problem for a $7 \times 7$ matrix, a solution would be:

$W_5= \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 &0\end{pmatrix}$

$W_4 = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$

$W_3= \begin{pmatrix} 0 & 0 & 0& 0 & 0 & 0 & 0\\ 0 & 0 & 0& 0 & 0 & 0 & 0\\ 0 & 0 & 0& 1 & 0 & 0 & 0\\ 0 & 0 & 0& 1 & 0 & 0 & 0\\ 0 & 0 & 0& 1 & 0 & 0 & 0\\ 0 & 0 & 0& 0 & 0 & 0 & 0\\ 0 & 0 & 0& 0 & 0 & 0 & 0\end{pmatrix}$

$W_2= \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0& 0\\ 0 & 0 & 0 & 0 & 0 & 0& 0\\ 0 & 0 & 0 & 0 & 0 & 0& 0\\ 0 & 0 & 1 & 1 & 1 & 0& 0\\ 0 & 0 & 0 & 0 & 0 & 0& 0\\ 0 & 0 & 0 & 0 & 0 & 0& 0\\ 0 & 0 & 0 & 0 & 0 & 0&0\end{pmatrix}$

$W_1= \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$

$W_0= \begin{pmatrix} 0 & 0& 0&0&0&0&0\\ 1 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$
Sune Kristian Jakobsen Says:
December 15, 2008 at 04:01 | Reply
I’ve just found out that every $5 \times 5$ matrix can be factorized into matrices with the above sparsity pattern: To prove this, you only have to prove that every matrix can be reduced to a diagonal matrix using elementary row and column operation, and that the matrices corresponding to the operations can be written as products of matrices with the given sparsity pattern (and of cause that diagonal matrices have the given sparsity pattern). Of cause this generalize to $n \times n$ matrices with a similar sparsity pattern.

However, I do not know how many factors you need. Can any $5 \times 5$ matrix be factorized into 4 matrices of the above form? And can any nxn matrix be factored into n-1 factors of this form?
Rod Carvalho Says:
December 15, 2008 at 10:32 | Reply
Sune,

A-ha! Row and column operations! How come I didn’t think of it?!

Your solution to my $5 \times 5$ is very elegant indeed. I really like the symmetry of it, i.e., $W_2 = W_1^T$ and $W_3 = W_0^T$ , and thus $A = W_0 ^T W_1^T W_1 W_0$ . The same operations performed on rows are also performed on columns. Beautiful!

Reducing a general $5 \times 5$ matrix $A$ to a diagonal matrix using elementary row and column operations sounds like a good idea. If I understand that right, what you are saying is that one can perform gaussian elimination on matrix $A$ and reduce it to a diagonal matrix $D = diag(d_1, d_2, \ldots, d_5)$ . In matrix form, these row and column operations are the same as multiplying $A$ on the left and right by elementary gaussian matrices $E_i, \tilde{E}_j \in \mathbb{R}^{5 \times 5}$ , i.e.

$(E_M E_{M-1} \ldots E_2 E_1) A (\tilde{E}_1 \tilde{E}_2 \ldots \tilde{E}_{N-1} \tilde{E}_{N}) = D$ ,

where the $E_i$ matrices perform operations on the rows of $A$ , and the $\tilde{E}_j$ matrices perform operations on the columns of $A$ . Since the elementary gaussian matrices are invertible, we have

$A = (E_1^{-1} E_2^{-1} \ldots E_{M-1}^{-1} E_M^{-1}) D (\tilde{E}_{N}^{-1} \tilde{E}_{N-1}^{-1} \ldots \tilde{E}_{2}^{-1} \tilde{E}_{1}^{-1})$ .

Like you wrote, the elementary gaussian matrices $E_i, \tilde{E}_j$ can be written as products of matrices with the given sparsity pattern. Thus, one has factorized $A$ into a finite number of matrices whose sparsity pattern is the desired one.
Rod Carvalho Says:
December 15, 2008 at 11:18 | Reply
Sune,

What if we use elementary row and column operations to reduce matrix $A$ to a matrix which has the desired sparsity pattern, but which is NOT diagonal? I believe that would allow us to obtain a factorization of $A$ with a minimum number of factors $W_i$ (a sort of “minimal factorization”). Do you agree?

You wrote:

However, I do not know how many factors you need. Can any 5×5 matrix be factorized into 4 matrices of the above form? And can any nxn matrix be factored into n-1 factors of this form?

I was not surprised that the solution you proposed had $4$ factors. The reason is that the diameter of this 1-dimensional linear chain with 5 nodes (an undirected graph) is $4$ .

The desired sparsity pattern is “encoded” in the topology of the graph linked above, i.e., if the $(i,j)$ entry of a factor matrix is constrained to be zero, then there will be no edge linking nodes $i$ and $j$ . The sparsity pattern in the example is “symmetric”, and thus it’s encoded in the topology of an undirected graph. In general, the desired sparsity pattern is “non-symmetric” and, hence, it is encoded in the topology of a directed graph. The edges have no weights, as all they tell us is whether certain entries of a matrix are free or constrained.

In fact, the adjacency and Laplacian matrices of the 1-dimensional linear chain linked above have the desired sparsity pattern. Note that the graph is connected, and thus, “information” from each node can reach any other node in, at most, $4$ steps (the diameter of the graph).

Suppose we now consider another sparsity pattern, one whose corresponding graph is not connected. Then, I believe that we would never be able to factorize the matrix $A$ in the example in a finite (or even infinite!) number of factors with the desired sparsity pattern. The only matrices we would be able to factorize into a finite number of matrices with the desired sparsity pattern would themselves have some sparsity pattern. This is based on intuition (I haven’t proved anything yet).

This graph-theoretic approach is quite interesting. For example, if there were no sparsity constraints at all, then the graph would be complete.
Sune Kristian Jakobsen Says:
December 15, 2008 at 12:24 | Reply
Rod,

What if we use elementary row and column operations to reduce matrix A to a matrix which has the desired sparsity pattern, but which is NOT diagonal? I believe that would allow us to obtain a factorization of A with a minimum number of factors W_i (a sort of “minimal factorization”). Do you agree?

Well, the product of two elementary matrices may be a sparse matrix: In the above example I copy the 2nd column to the first, and the 4th to the 5th in the same step. So the elementary matrices won’t be a minimal factorization. But I don’t know if you can get a minimal factorization if you multiply some of the elementary matrices.
Alex Says:
December 21, 2008 at 01:23 | Reply
Interesting problem. Given an arbitrary matrix and sparsity pattern, it sounds dauntingly NP. What motivates your interest?
- Rod Carvalho Says:
  December 21, 2008 at 01:43 | Reply
  Alex,
  
  Indeed, the general problem sounds quite hard. I started to think of this problem in Spring 2006. At the time I was doing some work on sensor networks and distributed estimation. I remember reading this paper by Stephen Boyd:
  
  Fast Linear Iterations for Distributed Averaging
  
  and wonder if it would be possible to do distributed averaging with time-varying matrices (a sort of a “controlled diffusion” on a graph). This problem naturally leads to the problem of factorizing a matrix into a finite number of factor matrices which have a certain sparsity pattern.
Jean-Marie Droz Says:
June 10, 2009 at 19:42 | Reply
It seems that a sparsity constraint $S$ is universal (allows factoring of any matrix) if and only it it has the following two properties:

- There is a permutation matrix $P$ that verifies the sparsity constraint.

- Some power of the matrix $U$ with one at each entry allowed by the constraint and zero elsewhere has all entries strictly positive.

I could have a constructive proof…

We note that both conditions are rather easy to check.

The smallest factorization of a matrix can in some cases be quadratic in the size of the matrix. Take for example as constraint for odd size $n$ , with free entries at $(3,1)$ , $(1,n)$ and $(1+j,j)$ for $j \in \{1,\dots,n-1\}$ . The constraint is universal, but obtaining the matrix with ones at $(1,1)$ and $(2,1)$ and zero elsewhere demands a long factorization $(O(n^2))$ .

In general, the number of elementary matrices you need to factorize a matrix is in $O(n^2)$ .

Rod Carvalho