Computing sparse orthogonal projections

Almost never compute matrix inverses, especially with sparse matrices. For something like this the most direct approach would be A * ((A'A) \ (A'x)) to multiply it by a vector x. If you want to precompute the LU factorization you could do LU = lu(A'A) and then compute A * (LU \ (A'x)). In some cases (if you have many more rows than columns), A'A may be dense, in which case you might want to use LU = lu(Matrix(A'A)) instead.

However, whether you are using sparse or dense matrices, you should strongly consider using the QR factorization for this kind of projection, in order to avoid explicitly computing A^* A and squaring the condition number (see also the discussion here). In particular, if the m\times n (n \le m) full-rank matrix A=\hat{Q}\hat{R} where \hat{Q} is m\times n, \hat{Q}^* \hat{Q} = I, and \hat{R} is square (n\times n) and invertible (i.e. the “thin” QR factorization), then A(A^* A)^{-1} A^* = \hat{Q}\hat{R} (\hat{R}^* \hat{R})^{-1} \hat{R}^* \hat{Q}^* = \boxed{\hat{Q}\hat{Q}^*}.

The QR = qr(A) function in Julia’s LinearAlgebra package computes the QR factorization, and SparseArrays provides an efficient method for sparse A as well. QR.Q represents the m\times m matrix Q of the “full” QR factorization, of which \hat{Q} is the first n columns — the matrix isn’t explicitly stored, but there are fast methods provided to multiply by Q and Q^*.

Thus, to obtain p = \hat{Q}\hat{Q}^* x for a vector x and a matrix A, do:

QR = qr(A)
y = QR.Q' * x
y[size(A,2)+1:end] .= 0 # project to y = Q̂'x
p = QR.Q * y

Unfortunately, it is somewhat more complicated in the sparse case, because in that case Julia computes a factorization P_r A P_c^* = QR \Longleftrightarrow A = P_r^{*} Q R P_c of a permuted version of the matrix A (where P_r and P_c are permutation matrices for the rows and columns of A, respectively). Hence the projection becomes A(A^* A)^{-1} A^* = \cdots = \boxed{P_r^{*} \hat{Q} \hat{Q}^* P_r}, which is computed by

QR = qr(A)
y = QR.Q' * x[QR.prow]   # compute y = Q'Pᵣx
y[size(A,2)+1:end] .= 0  # project to y = Q̂'Pᵣx
p = QR.Q * y
p[QR.prow] = p           # apply Pᵣᵀ permutation

Alternatively, realize that the intermediate step (A^*A)^{-1} A^* x is simply the least-squares solution. So, your projection can also be computed by:

p = A * (A \ x)

since A \ x does least-squares (via QR) for a matrix with more rows than columns. Or, using a precomputed QR factorization:

QR = qr(A)
p = A * (QR \ x)

This is closely related to the solution above involving Q, but may be slightly less efficient (and less accurate?) because it involves a (cheap) additional triangular solve step using the matrix \hat{R} (though this may be offset by the reduced cost of multiplying by A rather than Q).

16 Likes