Random solutions of undetermined linear systems

Question

Consider an underdetermined linear system of equations Ax=b.

I would like to find a set of vectors x_1, ..., x_n such that they all solve Ax=b and they are as different between each other as possible.

The second part is actually less important; I would be happy with an algorithm that returns a random solution of Ax=b every time I call it.

I know that scipy.sparse.linalg.lsqr and numpy.linalg.lstsq return a sparse solution (in terms of least squares) of an underdetermined linear system Ax=b, but I don't care about the properties of the solution; I just want any solution of Ax=b, as long as I can generate a bunch of different solutions.

In fact, scipy.sparse.linalg.lsqr and numpy.linalg.lstsq should follow an iterative process that jumps from a solution to an other until they find a solution that seems to be the minimum in terms of least squares. Well, is there a python module that lets me jump between solutions without a particular objective, and returns them?

Well, here it shows how you can compute the null space of `A` using Numpy and then generate random solutions yourself, pretty neat. http://stackoverflow.com/questions/33614378/how-can-i-obtain-the-same-special-solutions-to-underdetermined-linear-systems — Gioker, Apr 15 '17 at 07:27
http://scipy-cookbook.readthedocs.io/items/RankNullspace.html shows you how to find the null space of a matrix. Any linear combination of the columns of the null space is mapped by `A` to zero. So to get many solutions, take random linear combinations of the null space and add them to a least-squares solution. Then, `A . (xLS + colsOfNullspace . rand) = A . xLS = b`! With many of these, you can pick the ones that are most different using whatever matric you like. — Ahmed Fasih, Apr 15 '17 at 11:58
Maybe add a bit more information on what you exactly want to achieve. ```I would like to find a set of vectors x_1, ..., x_n such that they all solve Ax=b and they are as different between each other as possible.``` has no solution as the asking for as different each other increases the deviation on the right-hand side. It's a **multi-objective** optimization problem and without specifying the priority of these two objectives there is nothing to do. If you can specify this priority as a constant factor, it's a simple convex-optimization problem (with some assumptions about this *difference*). — sascha, Apr 15 '17 at 12:01

score 3 · Accepted Answer · edited May 23 '17 at 12:18

For the underdetermined system A·x = b you can compute the null space of your coefficient matrix A. The null space, Z, is a set of basis vectors spanning a subspace of A such that A·Z = 0. In other words, the columns of Z are vectors that are orthogonal to all of the rows in A. This means that for any solution x' to A·x = b, then x' + Z·c must also be a solution for any arbitrary vector c.

So if you wanted to sample random solutions to A·x = b then you could do the following:

Find any solution x' to A·x = b. You could do this using np.linalg.lstsq, which finds a solution that minimizes the L2 norm of x'.
Find the null space of A. There are a number of different ways to do this, most of which are covered in this previous question.
Sample a random vector c, and compute x' + Z·c. This will be a solution to A·x = b.

For example:

import numpy as np
from scipy.linalg import qr


def qr_null(A, tol=None):
    """Computes the null space of A using a rank-revealing QR decomposition"""
    Q, R, P = qr(A.T, mode='full', pivoting=True)
    tol = np.finfo(R.dtype).eps if tol is None else tol
    rnk = min(A.shape) - np.abs(np.diag(R))[::-1].searchsorted(tol)
    return Q[:, rnk:].conj()


# An underdetermined system with nullity 2
A = np.array([[1, 4, 9, 6, 9, 2, 7],
              [6, 3, 8, 5, 2, 7, 6],
              [7, 4, 5, 7, 6, 3, 2],
              [5, 2, 7, 4, 7, 5, 4],
              [9, 3, 8, 6, 7, 3, 1]])
b = np.array([0, 4, 1, 3, 2])

# Find an initial solution using `np.linalg.lstsq`
x_lstsq = np.linalg.lstsq(A, b)[0]

# Compute the null space of `A`
Z = qr_null(A)
nullity = Z.shape[1]

# Sample some random solutions
for _ in range(5):
    x_rand = x_lstsq + Z.dot(np.random.rand(nullity))
    # If `x_rand` is a solution then `||A·x_rand - b||` should be very small
    print(np.linalg.norm(A.dot(x_rand) - b))

Example output:

3.33066907388e-15
3.58036167305e-15
4.63775652864e-15
4.67877015036e-15
4.31132637123e-15

The space of possible c vectors is infinite - you'll have to make some choice as to how you want to sample these.

How to sample **_c_** in order to sample uniformly from **_x' + Zc_**? — Gioker, May 14 '17 at 09:00

score 2 · Answer 2 · answered Apr 15 '17 at 14:03

Here’s the code accompanying my comment. It uses the rank_nullspace.py module from the Scipy Cookbook.

import numpy as np
from numpy.linalg import lstsq

from rank_nullspace import nullspace
# rank_nullspace from
# http://scipy-cookbook.readthedocs.io/items/RankNullspace.html


def randsol(A, b, num=1, check=False):
    xLS, *_ = lstsq(A, b)

    colsOfNullspace = nullspace(A)
    nullrank = colsOfNullspace.shape[1]
    if check:
        assert(np.allclose(np.dot(A, xLS), b))
        assert(np.allclose(np.dot(A, xLS + np.dot(colsOfNullspace,
                                                  np.random.randn(nullrank))),
                           b))

    sols = xLS[:, np.newaxis] + np.dot(colsOfNullspace,
                                       np.random.randn(nullrank, num))
    return sols


A = np.random.randn(2, 10)
b = np.random.randn(2)
x = randsol(A, b, num=50, check=True)
assert(np.allclose(np.dot(A, x), b[:, np.newaxis]))

With a bunch of solutions in x, you can pick ones that are “different” from each other, however you define “different”.

Random solutions of undetermined linear systems

2 Answers2

Linked