Iteratively solving (sparse) homogeneous linear systems

Question

Solving (sparse) non-homogeneous linear systems can be done iteratively, by using the LSQR algorithm or similar. However, in the homogeneous case, we have $Ax =0$, where we typically want to find the non-zero solutions which is generally done by demanding a linear constraint on $x$, e.g. $|x|=1$. The method usually used to solve this constrained homogeneous system is by performing a singular value decomposition, and choosing the vector corresponding to the smallest singular value.

I'm looking for an iterative equivalent of LSQR that may be applied to sparse rectangular systems. LSQR does not seem appropriate, as it's stages implicitly assume $|b|\neq0$. Is anyone aware of such a method or can think of a method to modify LSQR appropriately?

Answer 1

You could use LSQR, by setting $b$, very close to zero (not exactly zero), which prevents, the trivial solution $(x = 0)$, In practice, it's a quite good approximation.

$Ax = \varepsilon$ ,

where $\varepsilon \approx 0$

ex. $\varepsilon = 10^{-7}$

In case of your application, requires an exact zero solution, then you might need to involve $m$ inequality constraints, $x > 0$, which could be solved easily using Lagrangian multipliers.

Answer 2

Looking through this paper, it gives a number of methods. The most straight forward seems to be the following algorithm:

1. Start with a random solution $x_0$
2. Break $A$ into it's QR decomposition, where Q is of size $m\times n$, and $R$ is upper diagonal
3. Solve via backwards substitution: $$R^Tw = x_{t-1}/|x_{t-1}|$$ $$R x_t = w$$
4. Iterate until convergence