SVD and Householder Reflections

[junoexpress]

Hi,

I have a question about how the SVD of a matrix is computed using
Householder reflections. The essential idea is that reduces the
original matrix to a bidiagonal form in a sequence of steps. At the
kth step, the appropriate elements of the kth column are zeroed out by
pre-multiplying by a Householder reflection, and then the appropriate
elements on the kth row are zeroed out by post-multiplying the matrix
by a Householder reflection. All of this makes sense and is perfectly
reasonable to me up to this point.
A condition however is placed on the Householder reflection that zeros
out the rows, which is that it cannot affect the zeros in the columns
(produced by the Householder reflections that pre-multiply the
original matrix). What guarantees that such a Householder reflection
exists?

(Below is an example illustrating the problem, if my description seems
confusing)

Let A be the 3x3 matrix:
x x x
A = x x x
x x x
so we want to pre-multiply A by Q1 where
Q1 is the Householder reflection that zeroes out the (2,1) and (3,1)
elements in column 1:
x x x
Q1 * A = 0 x x
0 x x
and V1 is the Householder reflection that zeroes out elements (1,2)
and (1,3) in first row
*without affecting the structure of zeros in the first column*, i.e.
x 0 0
Q1 * A * V1 = 0 x x
0 x x

The part I can't understand is what guarantees the existence of the
second Householder reflection. I know there is a Householder
reflection that will zero the first row appropriately, but what
guarantees that it will not affect the first column's structure?

TIA,

Matt

[Carl Barron]

In article
<2c342954-a983-4036...@l32g2000hse.googlegroups.com>,
junoexpress <MTBre...@gmail.com> wrote:

should be finding Q1 A V1 = x x 0
0 x x
0 x x

H = I - 2vv^T v^Tv = I

y = Hx = x - 2vv^Tx = x - 2(v^Tx) v

if v[k] = 0 then y[k] = x[k] - 2(v^Tx) v[k] = x[k] - 0 = x[k]

note the H = H^T -> y^T = x^T H^T = x^T H = x^T - 2(x^Tv)v^T

[Carl Barron]

In article
<2c342954-a983-4036...@l32g2000hse.googlegroups.com>,
junoexpress <MTBre...@gmail.com> wrote:

note also that if |y| == |x| the we can find v such that y = Hx
by choosing v = (y-x)/|y-x|

[junoexpress]

>
> should be finding Q1 A V1 = x x 0
> 0 x x
> 0 x x
>
> H = I - 2vv^T v^Tv = I
>
> y = Hx = x - 2vv^Tx = x - 2(v^Tx) v
>
> if v[k] = 0 then y[k] = x[k] - 2(v^Tx) v[k] = x[k] - 0 = x[k]
>
> note the H = H^T -> y^T = x^T H^T = x^T H = x^T - 2(x^Tv)v^T

Thanks.

Now that you write it out like that it seems obvious to me. Thus for
an NxN matrix, each new Vk matrix is really performing projections on
the set of row vectors {e_(k+1),,,e_N}, which will not affect the
already zeroed elements in {e_1,..,e_k}
I understood the notion that the successive Householder reflections
are really operating on block matrices of smaller dimensions, but
somehow, something didn't quite fully click until I saw your
solution.

Thank you again,

Matt