lsqminnorm

Minimum norm least-squares solution to linear equation

Syntax

X = lsqminnorm(A,B)

X = lsqminnorm(A,B,tol)

X = lsqminnorm(___,rankWarn)

Description

X = lsqminnorm(A,B) returns an array X that solves the linear equation AX = B and minimizes the value of norm(A*X-B). If several solutions exist to this problem, then lsqminnorm returns the solution that minimizes norm(X).

X = lsqminnorm(A,B,tol) additionally specifies the tolerance that lsqminnorm uses to determine the rank of A.

X = lsqminnorm(___,rankWarn) specifies an optional flag to display a warning if A has low rank. You can use any of the input argument combinations in previous syntaxes. rankWarn can be 'nowarn' (default) or 'warn'.

Examples

Solve Linear System with Infinite Solutions

Solve a linear system that has infinitely many solutions with backslash (\) and lsqminnorm. Compare the results using the 2-norms of the solutions.

When infinite solutions exist to $\mathrm{Ax}=\mathit{b}$, each of them minimizes $\Vert \mathrm{Ax}-\mathit{b}\Vert$. The backslash command (\) computes one such solution, but this solution typically does not minimize $\Vert \mathit{x}\Vert$. The solution computed by lsqminnorm minimizes not only norm(A*x-b), but also norm(x).

Consider a simple linear system with one equation and two unknowns, $2{\mathit{x}}_1+3{\mathit{x}}_2=8$. This system is underdetermined since there are fewer equations than unknowns. Solve the equation using both backslash and lsqminnorm.

A = [2 3];
b = 8;
x_a = A\b

x_a = 2×1

         0
    2.6667

x_b = lsqminnorm(A,b)

x_b = 2×1

    1.2308
    1.8462

The two methods obtain different solutions because backslash only aims to minimize norm(A*x-b), whereas lsqminnorm also aims to minimize norm(x). Calculate these norms and put the results in a table for easy comparison.

s1 = {'Backslash'; 'lsqminnorm'};
s2 = {'norm_Ax_minus_b','norm_x'};
T = table([norm(A*x_a-b); norm(A*x_b-b)],[norm(x_a); norm(x_b)],'RowNames',s1,'VariableNames',s2)

T=2×2 table
                  norm_Ax_minus_b    norm_x
                  _______________    ______

    Backslash                0       2.6667
    lsqminnorm      1.7764e-15       2.2188

This figure illustrates the situation and shows which solutions each of the methods return. The blue line represents the infinite number of solutions to the equation ${\mathit{x}}_2=-\frac{2}{3}{\mathit{x}}_1+\frac{8}{3}$. The orange circle represents the minimum distance from the origin to the line of solutions, and the solution returned by lsqminnorm lies exactly at the tangent point between the line and circle, indicating it is the solution that is closest to the origin.

Specify Tolerance to Reduce Impact of Noisy Data

Show how specifying a tolerance for the rank computation in lsqminnorm can help define the scale of the problem so that random noise does not corrupt the solution.

Create a low-rank matrix of rank 5 and a right-hand side vector b.

rng default % for reproducibility
U = randn(200,5);
V = randn(100,5);
A = U*V';
b = U*randn(5,1) + 1e-4*randn(200,1);

Solve the linear system $\mathrm{Ax}=\mathit{b}$ using lsqminnorm. Compute the norms of A*x-b and x to check the quality of the solution.

x = lsqminnorm(A,b);
norm(A*x-b)

ans = 0.0014

norm(x)

ans = 0.1741

Now add a small amount of noise to the matrix A and solve the linear system again. The noise affects the solution vector x of the linear system disproportionately.

Anoise = A + 1e-12*randn(200,100);
xnoise = lsqminnorm(Anoise,b);
norm(Anoise*xnoise - b)

ans = 0.0010

norm(xnoise)

ans = 1.1215e+08

The reason for the big difference in the solutions is that the noise affects the low-rank approximation of A. In other words, lsqminnorm is treating small values on the diagonal of the R matrix in the QR decomposition of A as being more important than they are. Ideally, these small values on the diagonal of R should be treated as zeros.

Plot the diagonal elements of the R matrix in the QR decomposition of Anoise. A large number of the diagonal elements are on the order of 1e-10.

[Q,R,p] = qr(Anoise,0);
semilogy(abs(diag(R)),'o')

The solution to this issue is to increase the tolerance used by lsqminnorm so that a low-rank approximation of Anoise with error less than 1e-8 is used in the calculation. This makes the result much less susceptible to the noise. The solution using a tolerance is very close to the original solution x.

xnoise = lsqminnorm(Anoise, b, 1e-8);
norm(Anoise*xnoise - b)

ans = 0.0014

norm(xnoise)

ans = 0.1741

norm(x - xnoise)

ans = 1.0811e-14

Toggle Warnings for Low-Rank Matrices

Solve a linear system involving a low-rank coefficient matrix with warnings turned on.

Create a 3-by-3 matrix that is of rank 2. In this matrix, you can obtain the third column by adding together the first two columns.

A = [1 2 3; 4 5 9; 6 7 13]

A = 3×3

     1     2     3
     4     5     9
     6     7    13

Find the minimum norm least-squares solution to the problem $\mathrm{Ax}=\mathit{b}$, where $\mathit{b}$ is equal to the second column in $\mathit{A}$. Specify the 'warn' flag for lsqminnorm to display a warning if it detects that A is of low rank.

b = A(:,2);
x = lsqminnorm(A,b,'warn')

Warning: Rank deficient, rank = 2, tol =  1.072041e-14.

x = 3×1

   -0.3333
    0.6667
    0.3333

Input Arguments

A — Coefficient matrix

matrix

Coefficient matrix. The coefficient matrix appears in the system of linear equations on the left as Ax = B. The coefficient matrix can be full or sparse.

Data Types: single | double
Complex Number Support: Yes

B — Input array

vector | matrix

Input array, specified as a vector or matrix. B appears in the system of linear equations on the right as Ax = B. If B is a matrix, then each column in the matrix represents a different vector for the right-hand side.

Data Types: single | double
Complex Number Support: Yes

tol — Rank tolerance

nonnegative scalar

Rank tolerance, specified as a nonnegative scalar. Specifying the tolerance can help prevent the solution from being susceptible to random noise in the coefficient matrix. By default, lsqminnorm computes tol based on the QR decomposition of A.

lsqminnorm computes the rank of A as the number of diagonal elements in the R matrix of the QR decomposition [Q,R,p] = qr(A,0) with absolute value larger than tol. If the rank of A is k, then the function forms a low-rank approximation of A by multiplying the first k columns of Q by the first k rows of R. Changing the tolerance affects this low-rank approximation of A.

Example: X = lsqminnorm(A,B,1e-2)

Data Types: double

rankWarn — Warning toggle for low-rank matrices

'nowarn' (default) | 'warn'

Warning toggle for low-rank matrices, specified as either 'nowarn' or 'warn'. Specify 'warn' to indicate that lsqminnorm should produce warnings if the coefficient matrix A is rank deficient.

Example: X = lsqminnorm(A,B,'warn')

Tips

• The minimum-norm solution computed by lsqminnorm is of particular interest when several solutions exist. The equation Ax = b has many solutions whenever A is underdetermined (fewer rows than columns) or of low rank.

• lsqminnorm(A,B,tol) is typically more efficient than pinv(A,tol)*B for computing minimum norm least-squares solutions to linear systems. lsqminnorm uses the complete orthogonal decomposition (COD) to find a low-rank approximation of A, while pinv uses the singular value decomposition (SVD). Therefore, the results of pinv and lsqminnorm do not match exactly.

• For sparse matrices, lsqminnorm uses a different algorithm than for dense matrices, and therefore can produce different results.