I have the problem of solving very large and very sparse least squares problems and, a bit dissatisfied with the run-times of the full-fledged QR-algorithm, I would like to bring the instances into block upper-triangular shape to be able to apply some generalized form of back-substitution (here the horizontal and the vertical side of the triangle have different length).
The generalized back-substitution would then start by solving the least squares problem that corresponds to the lowest right block and then proceed upwards, solving the least squares problem of the next higher block after substituting already determined variables.

I'm not sure, whether that idea is of any benefit, but out of curiosity I would like to know, if there is a good strategy for matrix reordering (i.e. row- and column permutations) that brings a matrix into block upper-triangular shape by only evaluating the matrix entries itself.

this question is related to Showing block diagonal structure of matrix by reordering, but it is not quite the same and the solution given there is based eigenvalues, which is not what I want to evaluate.

A problem, where Least Squares Problems with such a Block structure naturally appear, is the numerical inversion of Radon Transforms; here the variables correspond to pixels and equations to lines and the non-zero entries correspond to intersected pixels.
Lines, that go through pixels near the center of the transformed region also pass through pixels near the periphery of that region. The block structure thus resembles certain anuli of pixels.


I just found the article "Column Reordering for Box-Constrained Integer Least Squares Problems" by Stephen Breen and Xiao-Wen Chang (available online here: http://arxiv.org/abs/1204.1407), which addresses the topic of matrix reordering for Least Squares Problems, albeit for a special case.

Meanwhile, I devised the following heuristic for my problem:

  • define the "weight" of an unknown $c_0$ to be the number $j$ of different columns $c_j$, for which some row $r_i$ exists with $A[r_i][c_0]\ne 0 \wedge A[r_i][c_j]\ne 0$

  • sort the columns according to increasing weights of the corresponding unknowns.

  • sort the rows according to increasing number of leading zero-entries.

That heuristic manages to restore a full upper triangular square-matrix and thus seems a good starting point for further improvements.


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.