EE5120 Linear Algebra - Singular value decomposition

Now let \(A\) be any \(m\times n\) matrix, of rank \(r\). Step 1 still applies, since \(A^TA\) is symmetric whatever \(A\) is, and so does the calculation of Step 3, which used nothing about the columns of \(A\). What changes is that some \(Av_i\) may now be zero.

Claim 7.2. Let \(A\) be an \(m\times n\) matrix of rank \(r\), and let \(A^TAv_i = \lambda_iv_i\) with \(v_1,\ldots,v_n\) an orthonormal basis of \(\mathbb{R}^n\), as in Step 1. Then \(\lambda_i = \|Av_i\|^2 \geq 0\) for every \(i\), and exactly \(r\) of the \(\lambda_i\) are positive. For every \(i\) with \(\lambda_i = 0\), \(Av_i = 0\).

So we can number the eigenvalues as \(\lambda_1 \geq \cdots \geq \lambda_r > 0 = \lambda_{r+1} = \cdots = \lambda_n\), and \(\sigma_i = \sqrt{\lambda_i}\) gives exactly \(r\) nonzero singular values.

The lecture put this as: \(A\), \(A^TA\) and \(AA^T\) all have the same rank \(r\). The columns of \(AA^T\) are combinations of the columns of \(A\), and the rows of \(A^TA\) are combinations of the rows of \(A\), which shows only that neither product has rank larger than \(r\). Equality comes from Theorem 3.11, \(N(A^TA) = N(A)\): by Theorem 2.7, \(\operatorname{rank}(A^TA) = n - \dim N(A^TA) = n - \dim N(A) = r\), and the same argument applied to \(A^T\) gives \(\operatorname{rank}(AA^T) = \operatorname{rank}(A^T) = r\).

Run Steps 2 to 4 only for \(i = 1,\ldots,r\), where \(\lambda_i > 0\) and the division by \(\sigma_i\) is allowed. They give orthonormal vectors \(u_1,\ldots,u_r\) with \(Av_i = \sigma_iu_i\), and by the proof of Claim 7.2 these are a basis of \(C(A)\). For \(i > r\), Claim 7.2 gives \(Av_i = 0\). Step 6 goes through with \(r\) in place of \(n\): \(\dim N(A^T) = m - r\), and Gram—​Schmidt on a basis of it gives orthonormal \(u_{r+1},\ldots,u_m\), orthogonal to \(u_1,\ldots,u_r\). In Step 7, \(AV = \begin{bmatrix} \sigma_1u_1 & \cdots & \sigma_ru_r & 0 & \cdots & 0 \end{bmatrix}\), so the \((i,j)\) entry of \(U^TAV\) is \(\sigma_j\delta_{ij}\) for \(j \leq r\) and zero for \(j > r\). That is the matrix \(\Sigma\) of Theorem 7.1 with \(\sigma_{r+1} = \cdots = \sigma_p = 0\). Nowhere did this use \(m \geq n\), so Theorem 7.1 is now proved for every real matrix.

Take an SVD \(A = U\Sigma V^T\) and keep only the columns that go with nonzero singular values. Equation (2), and the same equation for \(A^T = V\Sigma^TU^T\), read

The first says that each \(u_i = Av_i/\sigma_i\) is a combination of the columns of \(A\); the second, that each \(v_i = A^Tu_i/\sigma_i\) is a combination of the rows of \(A\). The remaining columns of \(U\) and \(V\) fill in the two null spaces.

Theorem 7.3. Let \(A = U\Sigma V^T\) be an SVD of an \(m\times n\) matrix \(A\) of rank \(r\), as in Theorem 7.1. Then

Theorem 7.3 holds for every SVD of \(A\), not only the one constructed in the proof. The SVD is not unique (the signs of a pair \(u_i, v_i\) can be flipped together, for a start), and Matlab may return a different one from what a hand calculation gives.

Figure 1 is the picture of Chapter 2 (Figure 2 there) with something added. Chapter 2 found bases of the four subspaces by elimination, and Chapter 3 showed that they form two pairs of orthogonal complements. The SVD gives an orthonormal basis of all four at once, and matches the bases of the row space and the column space in pairs, \(v_i \mapsto \sigma_iu_i\). In the full column rank case of Section 2, \(r = n\), the null space is \(\{0\}\), and the vectors \(u_{n+1},\ldots,u_m\) of Step 6 are the basis of the left null space.

Let \(A\) be \(m\times \ell\) and \(B\) be \(n\times \ell\), so that both have \(\ell\) columns and \(AB^T\) is \(m\times n\). The usual rule is \((AB^T)_{ij} = \sum_k A_{ik}B_{jk}\): row \(i\) of \(A\) against row \(j\) of \(B\). There is a second way to group the same sum.

For a column \(g \in \mathbb{R}^m\) and a column \(h \in \mathbb{R}^n\), the outer product \(gh^T\) is the \(m\times n\) matrix with entries \((gh^T)_{ij} = g_ih_j\):

Every column of \(gh^T\) is a multiple of \(g\), so if \(g\) and \(h\) are nonzero, \(gh^T\) has rank one.

Now let \(a_k\) and \(b_k\) be column \(k\) of \(A\) and of \(B\). The \((i,j)\) entry of \(a_kb_k^T\) is \((a_k)_i(b_k)_j = A_{ik}B_{jk}\), which is the \(k\)-th term of the sum for \((AB^T)_{ij}\). Summing over \(k\):

A product of this shape is the sum of (column \(k\) of the first factor) times (column \(k\) of the second, transposed), one term for each \(k\). Chapter 1 wrote the same identity for a product \(AB\), as column \(k\) of \(A\) times row \(k\) of \(B\); that is (5) with \(B^T\) in place of \(B\). The form (5) suits factorizations that end in a transpose, where both factors are described by their columns: Chapter 5 used it on \((Q\Lambda)Q^T\) to write a symmetric matrix as \(\sum_i\lambda_iq_iq_i^T\), and the SVD is next.

Group (1) as \(A = (U\Sigma)V^T\), which has the shape of (5) with \(U\Sigma\) as the first factor and \(V\) as the second. The columns of \(U\Sigma\) are \(\sigma_1u_1,\ldots,\sigma_pu_p\), followed by zero columns if \(n > m\); the columns of \(V\) are \(v_1,\ldots,v_n\). By (5), and dropping the terms with \(\sigma_i = 0\),

So every matrix of rank \(r\) is a sum of \(r\) rank-one matrices, with weights \(\sigma_1 \geq \cdots \geq \sigma_r > 0\). For a symmetric positive definite matrix this is the expansion of Chapter 5, with \(u_i = v_i = q_i\); in general the left and right vectors differ.

Equation (6) can be written back as a product of smaller matrices. Let \(U_r = \begin{bmatrix} u_1 & \cdots & u_r \end{bmatrix}\) (\(m\times r\)), \(V_r = \begin{bmatrix} v_1 & \cdots & v_r \end{bmatrix}\) (\(n\times r\)) and \(\Sigma_r = \operatorname{diag}(\sigma_1,\ldots,\sigma_r)\). Then by (5) again, with first factor \(U_r\Sigma_r\) (columns \(\sigma_iu_i\)) and second factor \(V_r\),

This is the reduced SVD. The columns of \(U\) and \(V\) that it leaves out are bases of the two null spaces (Theorem 7.3), and in (1) they are multiplied by zeros.

Since the singular values decrease, the last terms of (6) carry the smallest weights. Keeping only the first \(k \leq r\) terms gives a matrix of rank \(k\),

When the singular values fall off quickly, the terms dropped carry small weights, and a small \(k\) gives a good approximation.

To store \(A_k\) we need \(k\) singular values and \(k\) pairs of vectors, \(k(m+n+1)\) numbers in all, against \(mn\) for \(A\). The example from class: a grey-scale image of \(1000\times 1000\) pixels is a matrix of \(10^6\) numbers. If \(k = 10\) terms are enough to make it recognisable, we need to send \(10\,(1000 + 1000) + 10 = 20010\) numbers, about \(50\) times fewer. Whether ten terms are enough depends on how fast the singular values of that image fall; the Matlab page tries it on a photograph.

If \(A\) is square and invertible, then \(r = m = n\), every \(\sigma_i > 0\), and

using \(U^{-1} = U^T\) and \((V^T)^{-1} = V\). For any other matrix \(\Sigma\) has no inverse, but there is an obvious substitute: invert the singular values that can be inverted. Let \(\Sigma^{ + }\) be the \(n\times m\) matrix with

and all other entries zero. The pseudo-inverse of \(A\) is

the sum coming from (5) as in (6). It is an \(n\times m\) matrix. By (8), \(A^{ + }u_i = v_i/\sigma_i\) for \(i \leq r\) and \(A^{ + }u_i = 0\) for \(i > r\): \(A^{ + }\) undoes \(A\) on the column space and sends the left null space to zero. Since the SVD is not unique, one may ask whether \(A^{ + }\) depends on which SVD was used to build it; the remark after Theorem 7.4 shows that it does not.

Suppose \(A\) is tall with independent columns, \(r = n < m\). Then \(\Sigma^{ + }\Sigma = I_n\), while \(\Sigma\Sigma^{ + } = \operatorname{diag}(1,\ldots,1,0,\ldots,0)\) is \(m\times m\) with \(n\) ones. So

and \(A^{ + }\) is a left inverse of \(A\); \(AA^{ + } = U\Sigma\Sigma^{ + }U^T\) is not \(I_m\). It is the left inverse of Chapter 2 (Theorem 2.11). By (3), \(A^TA = V(\Sigma^T\Sigma)V^T\) with \(\Sigma^T\Sigma = \operatorname{diag}(\sigma_1^2,\ldots,\sigma_n^2)\) invertible, so

because \((\Sigma^T\Sigma)^{-1}\Sigma^T\) is the \(n\times m\) matrix with diagonal entries \(\sigma_i/\sigma_i^2 = 1/\sigma_i\), which is \(\Sigma^{ + }\).

If instead \(A\) is fat with independent rows, \(r = m < n\), the same calculation with \(AA^T = U(\Sigma\Sigma^T)U^T\) gives \(AA^{ + } = I_m\) and \(A^T(AA^T)^{-1} = V\Sigma^T(\Sigma\Sigma^T)^{-1}U^T = A^{ + }\): the right inverse of Theorem 2.10. These are the two formulas in Chapter 3’s summary of the tall and fat cases, now given by one definition. Both need full rank. If \(r < n\) then \(A^{ + }A \neq I_n\), and if \(r < m\) then \(AA^{ + } \neq I_m\).

When the rank is deficient, \(\Sigma^{ + }\Sigma\) is the \(n\times n\) diagonal matrix with \(r\) ones followed by zeros, so by (5)

For a matrix \(Q\) with orthonormal columns, \(QQ^T\) is the projection onto \(C(Q)\) (Chapter 3). By Theorem 7.3, \(C(V_r) = C(A^T)\) and \(C(U_r) = C(A)\). So \(A^{ + }A\) is the projection onto the row space, and \(AA^{ + }\) is the projection onto the column space. Split \(x = x_r + x_n\) with \(x_r\) in the row space and \(x_n\) in the null space (Theorem 3.9); then \(A^{ + }Ax = x_r\). Chapter 3 said that \(A^{ + }A\) could not be the identity in general, and would instead throw away \(x_n\) and keep \(x_r\). This is that statement, proved.

In class the pseudo-inverse came with the summary "\(Ax = b \rightarrow x = A^{ + }b\)". When \(b \notin C(A)\) there is no solution, and \(A^{ + }b\) is to be read in the least squares sense of Chapter 3. The next theorem makes this precise for every \(A\), including rank deficient ones, where neither \(A^TA\) nor \(AA^T\) is invertible.

Theorem 7.4. Let \(A\) be an \(m\times n\) matrix and \(b \in \mathbb{R}^m\), and let \(\hat x = A^{ + }b\). Then \(\hat x\) minimises \(\|Ax - b\|\) over all \(x \in \mathbb{R}^n\), and every other minimiser \(x\) has \(\|x\| > \|\hat x\|\).

The minimiser of least length is a property of \(A\) and \(b\) alone, so \(A^{ + }b\) is the same for every SVD of \(A\); since this holds for every \(b\), so is \(A^{ + }\). When the columns of \(A\) are independent there is only one minimiser, and it is the least squares solution of Theorem 3.12. When the rows are independent the least error is zero, and \(A^{ + }b\) is the minimum norm solution of Theorem 3.14. When neither holds, \(A^{ + }b\) does both jobs: least error, and among those the least length.

By (8),

Each term is a scalar, \(u_i^Tb/\sigma_i\), times a vector, \(v_i\). The component of \(b\) along \(u_i\) is divided by \(\sigma_i\), so the smallest singular values have the largest influence on the solution. A small change in \(b\) along \(u_r\) changes \(\hat x\) by that change divided by \(\sigma_r\). The next section measures this.

Let \(A\) be square and invertible, and suppose the right hand side of \(Ax = b\) is known only up to an error \(\Delta b\), from measurement or from round off. Then we actually solve \(A(x + \Delta x) = b + \Delta b\), and subtracting \(Ax = b\) gives \(A\,\Delta x = \Delta b\), that is \(\Delta x = A^{-1}\Delta b\). We quantify errors with the length \(\|\cdot\| = \|\cdot\|_2\), and compare relative errors:

The condition number \(\kappa(A)\) is the largest value of (10) over all \(b \neq 0\) and \(\Delta b \neq 0\). It is the worst factor by which a relative error in the data can grow into a relative error in the solution. Note that \(\kappa\) is a property of \(A\) alone; no algorithm enters.

Theorem 7.5. Let \(A\) be an invertible \(n\times n\) matrix with singular values \(\sigma_1 \geq \cdots \geq \sigma_n > 0\). Then

The maximum of (10) is reached at \(b = u_1\) and \(\Delta b = u_n\) (or any nonzero multiples of these).

So \(\kappa(A) \geq 1\) always, with equality when all the singular values are equal, as for an orthogonal matrix. A singular matrix has no inverse, and its condition number is taken to be \(\infty\). As a working rule, the class took a matrix with \(\kappa > 10^4\) to be ill conditioned; there is no sharp line, but a relative error of \(10^{-6}\) in \(b\) can then become \(10^{-2}\) in \(x\).

Chapter 1 described the condition number as \(\|A\|\,\|A^{-1}\|\), and Chapter 3 pointed out that the Frobenius norm is not the matrix norm that measures how much \(A\) can stretch a vector. The norm that does is

Claim 7.6. For any \(m\times n\) matrix \(A\), \(\|A\|_2 = \sigma_1\), and the maximum is reached at \(x = v_1\).

The two factors in the proof of Theorem 7.5 are exactly these norms. The largest value of the first factor is \(\|A^{-1}\|_2 = 1/\sigma_n\), the largest singular value of \(A^{-1} = V\Sigma^{-1}U^T\). For the second, put \(x = A^{-1}b\); then \(\|b\|/\|A^{-1}b\| = \|Ax\|/\|x\|\), whose largest value is \(\|A\|_2 = \sigma_1\). So

which is the formula of Chapter 1, with the norm now specified and computed.

The matrix

is triangular, with both eigenvalues equal to \(1\) and determinant \(1\). Nothing about these numbers suggests trouble. Solve \(Ax = b\) for two nearby right hand sides:

(Check the second: \((1)(-9) + (1000)(0.01) = 1\).) A change of \(1\%\) in \(b\) has changed the first entry of \(x\) from \(1\) to \(-9\). In terms of (10), \(\Delta x = (-10, 0.01)\), so the ratio is \(\sqrt{100.0001}\,/\,0.01 \approx 1000\).

The singular values explain it. They are the square roots of the eigenvalues of

Its trace and determinant give \(\sigma_1^2 + \sigma_2^2 = 1000002\) and \(\sigma_1^2\sigma_2^2 = 1\), so \(\sigma_1\sigma_2 = 1\) and \((\sigma_1 - \sigma_2)^2 = 1000002 - 2 = 10^6\). Hence \(\sigma_1 - \sigma_2 = 1000\), and

In round numbers \(\sigma \approx 10^3, 10^{-3}\) and \(\kappa \approx 10^6\): a badly conditioned matrix whose eigenvalues are both \(1\).

The perturbation above was amplified by about \(1000\), not \(10^6\). In the proof of Theorem 7.5, its first factor is close to its largest value \(1/\sigma_2 \approx 1000\), but its second factor is \(\|b\|/\|x\| = 1\), far from the largest value \(\sigma_1 \approx 1000\). To approach the worst case, take \(b\) close to the direction \(u_1\) as well, for instance \(b = A(0,1)^T = (1000, 1)^T\). Then \(x = (0,1)^T\), and the same \(\Delta b = (0, 0.01)^T\) gives the same \(\Delta x = (-10, 0.01)^T\). The relative change in \(b\) is now \(0.01/\sqrt{1000001} \approx 10^{-5}\), the relative change in \(x\) is about \(10\), and the ratio is about \(10^6\).

For a tall matrix \(A\) with independent columns, (10) does not apply as it stands, since \(A^{-1}\) does not exist. The same ratio of singular values, \(\kappa(A) = \sigma_1/\sigma_n\), is taken as its condition number (it is what Matlab’s cond computes). Solving least squares through the normal equations \(A^TAx = A^Tb\) replaces \(A\) by \(A^TA\). By (3), \(A^TA = V(\Sigma^T\Sigma)V^T\): a symmetric positive definite matrix whose SVD is its eigenvalue decomposition, with singular values \(\sigma_1^2 \geq \cdots \geq \sigma_n^2\). So

A bad condition number becomes much worse: \(\kappa(A) = 10^4\) becomes \(\kappa(A^TA) = 10^8\). This is the reason, given without proof in Chapter 3, for solving least squares by \(QR\) rather than through \(A^TA\), and it is why svd routines do not form \(A^TA\) either.

Keep only the first \(k \leq r\) terms:

This is \(A_k^{ + }b\), the pseudo-inverse of the rank \(k\) matrix \(A_k\) of Section 4.3 applied to \(b\). Dropping the terms with small \(\sigma_i\) throws away the part of the solution along \(v_{k+1},\ldots,v_r\), and with it the amplified noise in those directions. Too small a \(k\) loses real information; too large a \(k\) lets the noise back in; \(k = r\) gives \(A^{ + }b\) again. There is no formula for the right \(k\) — in the words of the lecture, choosing it is like cooking! One looks at how the singular values fall and at what the solutions look like for a few values of \(k\).

Instead of cutting the terms off, damp them. For a number \(\alpha > 0\), minimise

The first term asks for a small error, as in least squares; the second penalises a long \(x\), which is what the amplified noise produces. (The lecture wrote \(\lambda\) for \(\alpha\); in this chapter \(\lambda_i\) already denotes the eigenvalues of \(A^TA\).) The two terms are the two pieces of one least squares problem,

with an \((m+n)\times n\) matrix whose columns are independent, because of the block \(\alpha I\). By Theorem 3.12 the minimiser is unique and solves the normal equations

Now substitute the SVD. By (3), \(A^TA + \alpha^2I = V(\Sigma^T\Sigma + \alpha^2I)V^T\), and \(A^Tb = V\Sigma^TU^Tb\). The matrix \(\Sigma^T\Sigma + \alpha^2I\) is diagonal with entries \(\sigma_i^2 + \alpha^2 > 0\) (with \(\sigma_i = 0\) for \(i > r\)), and the vector \(\Sigma^TU^Tb\) has entries \(\sigma_i\,u_i^Tb\), which are zero for \(i > r\). So \(V^Tx\) has entries \(\sigma_i\,u_i^Tb/(\sigma_i^2 + \alpha^2)\), and

Compare (9): the factor \(1/\sigma_i\) has become

The second fraction is close to \(1\) when \(\sigma_i \gg \alpha\), so those terms are left almost as they were, and close to \(0\) when \(\sigma_i \ll \alpha\), so those terms are suppressed. Tikhonov regularisation is a smooth version of truncation, with the cut placed near \(\sigma_i \approx \alpha\). As \(\alpha \rightarrow 0\), \(\hat x_\alpha \rightarrow A^{ + }b\). Choosing \(\alpha\) is the same kind of cooking as choosing \(k\).

Data goes out as a stream of complex numbers called symbols, one every symbol period (a fixed short time). In each symbol period, transmit antenna \(j\) sends a complex number \(x_j\), and receive antenna \(i\) picks up a combination of all of them, plus noise:

with \(x \in \mathbb{C}^n\), \(y, w \in \mathbb{C}^m\), and \(H\) an \(m\times n\) complex matrix: one row for each receive antenna and one column for each transmit antenna. The entry \(h_{ij}\) is the gain and phase shift from transmit antenna \(j\) to receive antenna \(i\). (The signals are in complex baseband form, where one complex number carries the amplitude and the phase of a sinusoid.) The vector \(w\) is the noise at the receive antennas. We assume the following.

The transmitter has \(r\) data symbols \(s = (s_1,\ldots,s_r)\) to send in each symbol period. Instead of putting them on the antennas directly, it sends

where \(V_r\) holds the first \(r\) columns of \(V\), as in (7). Symbol \(s_i\) goes out along \(v_i\). The matrix \(V_r\) is the precoder. The receiver multiplies what it receives by the decoder \(U_r^H\), to get \(\tilde y = U_r^Hy\). From \(H = U\Sigma V^H\) we have \(U^HHV = \Sigma\), and \(U_r^HHV_r\) is the top left \(r\times r\) block of it, \(\Sigma_r = \operatorname{diag}(\sigma_1,\ldots,\sigma_r)\). So, with \(\tilde w = U_r^Hw\),

Since \(\Sigma_r\) is diagonal, this is \(r\) separate equations,

Symbol \(s_i\) reaches output \(i\), multiplied by \(\sigma_i\), and reaches no other output. The channel \(H\), which mixes every transmit antenna into every receive antenna, now behaves as \(r\) scalar channels side by side, each with its own gain \(\sigma_i\). To recover \(s_i\), the receiver divides \(\tilde y_i\) by \(\sigma_i\). Figure 2 draws the scheme.

The number of symbols is \(r\), and not more, for two reasons.

So the number of data streams that can be sent at the same time is the rank, \(r \leq \min(m,n)\). Antennas added at one end cannot raise it beyond the number at the other end, and more antennas at both ends do not by themselves give more streams. If the antennas at each end are close together and the signal travels to a distant receiver along a single line-of-sight path, the columns of \(H\) are nearly parallel, and \(H\) is close to rank one: one large singular value and the rest small. Close, but not equal: a channel matrix found by measurement is almost never exactly rank deficient, because small random changes in its entries, from estimation errors or from the surroundings, make the zero singular values nonzero. So in practice \(r = \min(m,n)\), and how many streams are worth using depends on how small the trailing \(\sigma_i\) are, not on the exact rank (Section 8.4 says more). Several streams need signals arriving from several directions, as in a city full of reflecting buildings.

The precoder and the decoder change neither the power sent nor the noise in each stream.

This subsection is optional; nothing else in the notes depends on it.

Suppose the transmitter sends a single symbol \(s\) of power \(P = \mathrm{E}[|s|^2]\) along a unit vector \(t \in \mathbb{C}^n\): \(x = ts\), so that the transmitted power is also \(P\). The signal part of \(y\) is \(Hts\), of length \(\|Ht\|\,|s|\). By Claim 7.6, \(\|Ht\| \leq \sigma_1\) for every unit vector \(t\), with equality at \(t = v_1\). So sending along \(v_1\) gives the strongest received signal, \(Hv_1s = \sigma_1u_1s\). The receiver then takes

which keeps all of the signal. By the rule of Section 8.2 with \(M = u_1^H\), the noise \(u_1^Hw\) has variance \(u_1^H(N_0I)u_1 = N_0\), so the signal to noise ratio (signal power divided by noise power) is \(\sigma_1^2P/N_0\). This is beamforming: \(v_1\) points the transmitted power in the direction that the channel passes best, and \(u_1\) collects it at the receiver. It is stream 1 of (17) used alone, with all the power on it.

This subsection is optional; nothing else in the notes depends on it.

In (17), stream \(i\) has signal power \(\sigma_i^2P_i\), where \(P_i = \mathrm{E}[|s_i|^2]\) is the power the transmitter puts on it, and noise power \(N_0\), so its signal to noise ratio is \(\sigma_i^2P_i/N_0\). With equal power on every stream, the streams with small \(\sigma_i\) have a low signal to noise ratio and make many errors; the Matlab page shows this. The transmitter knows the \(\sigma_i\) and can act on them: it can send fewer bits on a weak stream, give it less power, or leave it unused and give its power to the strong streams. Leaving out the streams with small \(\sigma_i\) is the truncated SVD of Section 7.1 again, in a different setting.

How best to share a total power \(P = P_1 + \cdots + P_r\) among the streams is a question for a course on communication, and we only quote the answer here, without proof. When the noise is Gaussian, the highest rate at which data can be sent reliably over this channel, in bits per symbol period, is the largest value of

over all \(P_i \geq 0\) with \(P_1 + \cdots + P_r = P\). Each term is the rate of one scalar channel of (17), so the link carries the sum of what its \(r\) streams carry. The best powers, given by a rule called water-filling, give a weaker stream less power, and none at all if it is weak enough.

This subsection is optional; nothing else in the notes depends on it.

The scheme above needs \(V\) at the transmitter. Zero forcing is a standard scheme that needs \(H\) only at the receiver. Let \(m \geq n\) and let \(H\) have independent columns, so that \(r = n\). The transmitter puts the symbols directly on the antennas, \(x = s\) with \(s \in \mathbb{C}^n\), and the receiver multiplies \(y\) by the left inverse \(H^{ + } = (H^HH)^{-1}H^H\) of Section 5.2, with \({}^H\) in place of \({}^T\):

Each estimate \(\hat s_j\) contains \(s_j\) and noise, and nothing of the other symbols: the interference between the streams is forced to zero, which is where the name comes from.

The two schemes differ in the noise. By the rule of Section 8.2 with \(M = H^{ + } = V\Sigma^{ + }U^H\), and \(U^HU = I\),

The matrix \(\Sigma^{ + }(\Sigma^{ + })^H\) is \(n\times n\) and diagonal, with entries \(1/\sigma_i^2\). So the noise in \(\hat s_j\), the \(j\)-th diagonal entry, has variance (with \(V_{ji}\) the entry of \(V\) in row \(j\) and column \(i\))

The rows of the unitary matrix \(V\) have unit length (Chapter 5), so \(\sum_i |V_{ji}|^2 = 1\), and this is \(N_0\) times a weighted average of the numbers \(1/\sigma_i^2\), as in the proof of Theorem 7.5. In the SVD scheme, dividing (17) by \(\sigma_i\) gives \(s_i + \tilde w_i/\sigma_i\), with noise variance \(N_0/\sigma_i^2\). Added over the streams, both schemes have total noise variance \(N_0\sum_i 1/\sigma_i^2\) (for zero forcing, add the weighted averages over \(j\) and use that the columns of \(V\) also have unit length). They share it out differently. Zero forcing spreads the large term \(N_0/\sigma_n^2\) of the weak direction \(v_n\) over all the streams; the SVD scheme keeps it on stream \(n\) alone. Since a weighted average of the \(1/\sigma_i^2\) cannot exceed the largest of them, \(1/\sigma_n^2\), the weakest SVD stream is at least as noisy as every zero forcing stream. So with the same power and the same kind of symbols on every stream, zero forcing can make fewer errors in all, and the Matlab page has an example. The SVD scheme gains when the transmitter acts on what it knows about the \(\sigma_i\), as in Section 8.4, by giving the weak stream fewer bits, less power or none. A zero forcing transmitter does not know \(V\), so it cannot move its power between the directions \(v_i\); at most it can act antenna by antenna, which is not the same thing.