In a recent blog post What is ?, Cleve Moler asked what the MATLAB operation returns. I will summarize what backslash does in general, for and then consider the case .
is a solution, in some appropriate sense, of the equation
It suffices to consider the case , because backslash treats the columns independently, and we write this as
The MATLAB backslash operator handles several cases depending on the relative sizes of the row and column dimensions of and whether it is rank deficient.
When is square, backslash returns , computed by LU factorization with partial pivoting (and of course without forming ). There is no special treatment for singular matrices, so for them division by zero may occur and the output may contain NaNs (in practice, what happens will usually depend on the rounding errors). For example:
>> A = [1 0; 0 0], b = [1 0]', x = A\b A = 1 0 0 0 b = 1 0 Warning: Matrix is singular to working precision. x = 1 NaN
Backslash take advantage of various kinds of structure in ; see MATLAB Guide (section 9.3) or
doc mldivide in MATLAB.
An overdetermined system has no solutions, in general. Backslash yields a least squares (LS) solution, which is unique if has full rank. If is rank-deficient then there are infinitely many LS solutions, and backslash returns a basic solution: one with at most nonzeros. Such a solution is not, in general, unique.
An underdetermined system has fewer equations than unknowns, so either there is no solution of there are infinitely many. In the latter case produces a basic solution and in the former case a basic LS solution. Example:
>> A = [1 1 1; 1 1 0]; b = [3 2]'; x = A\b x = 2.0000e+00 0 1.0000e+00
Another basic solution is , and the minimum -norm solution is .
Now we turn to the special case , which in terms of equation (1) is a solution to . If then is not a basic solution, so ; in fact, if and it is matrix of NaNs if .
For an underdetermined system with full-rank , is not necessarily the identity matrix:
>> A = [1 0 1; 0 1 0], X = A\A A = 1 0 1 0 1 0 X = 1 0 1 0 1 0 0 0 0
But for an overdetermined system with full-rank , is the identity matrix:
>> A'\A' ans = 1.0000e+00 0 -1.9185e-17 1.0000e+00
Minimum Frobenius Norm Solution
The MATLAB definition of is a pragmatic one, as it computes a solution or LS solution to in the most efficient way, using LU factorization () or QR factorization ). Often, one wants the solution of minimum -norm, which can be expressed as , where is the pseudoinverse of . In MATLAB, can be computed by
pinv(A)*b, the former expression being preferred as it avoids the unnecessary computation of and it uses a complete orthogonal factorization instead of an SVD.
When the right-hand side is a matrix, ,
pinv(A)*B give the solution of minimal Frobenius norm, which we write as . Then , which is the orthogonal projector onto , and it is equal to the identity matrix when and has full rank. For the matrix above:
>> A = [1 0 1; 0 1 0], X = lsqminnorm(A,A) A = 1 0 1 0 1 0 X = 5.0000e-01 0 5.0000e-01 0 1.0000e+00 0 5.0000e-01 0 5.0000e-01
Related Blog Posts
- What Is an LU Factorization? (2021)
- What Is a QR Factorization? (2020)
- What Is a Rank-Revealing Factorization? (2021)