376 CHAPTER 13. MATRICES AND THE INNER PRODUCT
One obviously minimizes this error by letting h = 0 = xi for all i ̸= j. That is, the columnshould have all zeroes with σ j in the diagonal position. As to any columns of B̃ whichare not pivot columns, such a column is a linear combination of these basis columns whichhave exactly one entry, in the diagonal position. These non pivot columns must have a 0in the diagonal position since if not, the rank of the matrix would be more than l. Thenthe off diagonal entries should equal zero to make the approximation as good as possible.Thus the non basis columns are columns consisting of zeros and B̃ is a diagonal matrixwith l nonzero diagonal entries selected from the first r columns of A. It only remains toobserve that, since the singular values decrease in size from upper left to lower right in A,to minimize the error, one should pick the first l columns for the basis for B̃ in order to usethe sum of the squares of the smallest possible singular values in the error. That is, youwould replace σ r×r with the upper left l× l corner of σ r×r.
A =
(σ r×r 0
0 0
),⇒ B̃ =
(σ l×l 0
0 0
)
For example, consider 3 0 0 00 2 0 00 0 1 0
The best rank 2 approximation is 3 0 0 0
0 2 0 00 0 0 0
Now suppose A is an m×n matrix. Let U,V be unitary and of the right size such that
U∗AV =
(σ r×r 0
0 0
)
Then suppose B approximates A as well as possible in the Frobenius norm, B having rankl < r. Then you would want
∥A−B∥= ∥U∗AV −U∗BV∥=
∥∥∥∥∥(
σ r×r 00 0
)−U∗BV
∥∥∥∥∥to be as small as possible. Therefore, from the above discussion, you should have
B̃≡U∗BV =
(σ l×l 0
0 0
),B =U
(σ l×l 0
0 0
)V ∗
whereas
A =U
(σ r×r 0
0 0
)V ∗