Handling of non-square `AbstractQ`

[araujoms]

I'm not sure whether this is a bug or intentional, but the handling of non-square AbstractQ is rather inconsistent.

import LinearAlgebra.QRPackedQ
q = QRPackedQ(randn(4,3),randn(3))
size(q) != size(Matrix(q))
size(Matrix(q')) != size(Matrix(q)')
size(Matrix(q')*Matrix(q)) != size(q'*q)
size(Matrix(q)'*Matrix(q)) != size(q'*q)
size(Matrix(q')*Matrix(q)) != size(Matrix(q)'*Matrix(q))
s = QRPackedQ(randn(5,4),randn(4))
size(Matrix(s)*Matrix(q)) != size(s*q)

[dkarrasch]

Without going through the list in detail, I suspect that most of it is intentional, though the intention may be misguided. In that case a concrete argument/use case would be helpful for reconsideration. Matrix(q) may return a non-square representation (as the docstring says), whereas in some of those operations (like q'q), where you need to make one of the factors a matrix to apply the other factor, we use its size, which is square IIRC, for the matrixification.

[araujoms]

My intention was to use QRPackedQ to represent an isometry, so I need the non-square representation. Doesn't look like it's possible without reimplementing everything, though.

[dkarrasch]

But aren't both representations/shapes isometries? The current behaviour is very old Julian behaviour. Matrix(q) may yield non-square, collect(q) always returns the square version of it. For many operations, you need make a choice about what should be the standard size, and that choice has always (AFAIR) been the square version.

[araujoms]

An isometry is a d x k matrix V such that V'*V = I (and k <= d). A unitary is a particular case of an isometry where d == k. If you take the QR decomposition of a d x k matrix, the result is a d x k isometry and a k x k upper triangular. A d x k isometry can be represented by a sequence of k Householder reflections, so it fits perfectly as a QRPackedQ with a d x k factor and a k-element vector τ. I assume this is why Matrix(q) displays the d x k isometry.

If this is old behaviour I assume it's unlikely to change, but I don't see where it would be useful to regard it as a d x d matrix instead. Also, as my examples show, this is done very inconsistently. I don't see why Matrix(q) should be d x k but suddenly Matrix(q') should be d x d instead of k x d. My last example is specially strange: when computing s*q only the second matrix is converted to a square, the first stays 5 x 4. It gets even weirder if you do q'*s'. Now both matrices are converted to squares, and we get an error that the dimensions are incompatible.

[dkarrasch]

Sure, but Householder reflections are naturally square, so you get the square matrix representation out of the very same data.

As for the Matrix(q') case, that is debatable. Traditionally, we build the matrix representation from left multiplication. It is for this order that QRPackedQ can be both d x k and d x d, but there is no such "ambiguity" for its adjoint (for multiplication from the left). Instead, the adjoint has the corresponding size ambiguity for multiplication from the right.

And the case q'*s' is again difficult: if both factors have size ambiguity, which one do you pick, and why?

At least, and I'm somewhat happy about that because I did a major AbstractQ overhaul in v1.10, your tests in the OP are consistent across the versions.

[dkarrasch]

Would be interesting to know what other languages do about it (Python, Matlab)...

[araujoms]

Sure, the same Householder reflections also define a square matrix, what I'm asking is whether is it useful for anything. I don't think so. I just looked it up, and Python (numpy) by default returns a non-square matrix, whereas MATLAB by default returns a square matrix. Both have can return the other one as an option. And neither can handle the Householder reflections efficiently, so kudos to you there.

I'm aware of your AbstractQ overhaul, it was pretty nice. It's what made me decide to subtype AbstractQ to produce random unitaries efficiently in my package. Now I was trying to extend it to isometries.

I don't think defaulting to left multiplication is a good reason to choose anything. Computational complexity might be a good reason, but it's the same for both cases. I think consistency with Matrix(q) is a much better reason.

As for q'*s', I don't think the question is difficult. One option produces an error, the other a useful result. Moreover, the latter is consistent with Matrix(s*q).

[sethaxen]

I also prefer that AbstractQ reflects the size of the Q matrix of the factorization, not the full matrix represented by the reflectors. Take QR as an example. To me it makes most sense that A=QR i.e. I can multiply Q*R to get back A. I can do that now, but only because of the size-inconsistency. There's currently no API for me to access what size matrix Q would need to correspond to for me to get back A without calling Matrix(Q). This is wasteful.

Here's a concrete case where this matters. The density of distributions on the semi-orthogonal matrices (Stiefel manifold) are typically defined wrt the so-called invariant measure. One can sample from the normalized invariant measure on Stiefel(n, k) with Q = qr_unique(randn(n, k)).Q, where qr_unique could use the same algorithm as xGEQRFP to build a QR whose R has a positive diagonal. Matrix(Q) follows the desired measure. However, Q*I does not follow the normalized invariant measure on Stiefel(n, n). For many applications it will be much more efficient to use Q directly, but there's currently no way to even tell what k was, so we don't even know which manifold it is from.

An alternative (breaking) proposal to what LinearAlgebra currently does would be:

1. Give each concrete AbstractQ implementation the size corresponding to the Q matrix as it would appear in the factorization
2. Introduce a SquareQ (or something) wrapper that allows Q to be explicitly interpreted as square for types and operations that support it.

The advantage of this approach is that it covers all of the same functionality as the current approach, but it doesn't discard the information about the size of the equivalent Q matrix in the factorization. It also eliminates all ambiguity in the size of Q.

An alternative non-breaking approach would be to add a factor_size(::AbstractQ) API function (probably a better name) that just returns the size of the matrix as it would appear in the factorization.

Edit: Yet another non-breaking approach would be to add a MatrixQ struct (either subtype of AbstractMatrix or AbstractQ) that just interprets the wrapped AbstractQ as the non-square version. But I do think this is less elegant than the breaking one described above because the original AbstractQ still has the ambiguity in behavior.