`spaugment`

Augmented matrix of the least-squares problem for a sparse matrix.

Syntax

S = spaugment(A)

Returns [speye(m) A; A' sparse(n,n)] for an m-by-n matrix A.

S = spaugment(A, c)

Uses c*speye(m) in the upper left block.

Description

The least-squares problem of minimizing norm(b - A*x) can be written as one symmetric indefinite linear system in the unknowns r (residual) and x. spaugment builds the coefficient matrix of that system, so that sparse direct or iterative solvers can be applied without squaring the condition number as the normal equations do.

With c as the scaling, the system is S*[r/c; x] = [b; 0].

Input arguments

A: Sparse (or full) m-by-n matrix.
c: Scalar scaling the identity block; the default is max(abs(A(:)))/1000.

Output arguments

S: Symmetric sparse matrix of size (m+n)-by-(m+n).

Example

Augmented matrix of a 3-by-2 matrix

A = sparse([1 2; 3 4; 5 6]);
S = spaugment(A, 1);
full(S)

Output

ans = 5×5

     1     0     0     1     2
     0     1     0     3     4
     0     0     1     5     6
     1     3     5     0     0
     2     4     6     0     0

spaugment