Quadratic Knapsack
- PDF / 8,441,790 Bytes
- 101 Pages / 594 x 828 pts Page_size
- 53 Downloads / 217 Views
Properties of Orthogonal Transforms. Orthogonal t r a n s f o r m s are where the transformation
matrices are orthogonal. Orthogonal matrices are square matrices where each column is a unit vector and each column is mutually orthogonal to every other column. This implies that Q E R n×n is orthogonal if and only if Q T Q = Q Q T = I (i.e. the transpose of an orthogonal matrix is its inverse). Orthogonal transformations are invariant under the 2-norm; i.e. []Qx[[2 = [[x[[2. More details can be found in [8]. There are two popular orthogonal transformations: Householder and Givens.
Householder
Transformations. These are named after A.S. Householder, who popularized their use in matrix computations. However, the properties of these matrices have been known for quite some time. For any nonzero v E R n, a matrix H of the form H=I_2
vv-r
VTV
is called H o u s e h o l d e r t r a n s f o r m a t i o n . It is easy to verify that H is symmetric, and orthogonal (which also means that it is its own inverse). Identity matrices are not Householder matrices. Geometrically, Householder matrices merely rotate a given vector in n-dimensions (without stretching or shrinking). Given any two vectors x and
y such that [[x[[2 = [[YH2, there exists a Householder transformation H such that H x = y (it is easy to verify that v = y - x satisfies this equation). Note that v completely characterizes H (in the sense that even though H is an n × n matrix, v is enough to reconstruct H, and to apply H). Also, scaling v by a scalar factor a will not change the transformation H.
QR Factorization using Householder Transformations. Since Householder transformations rotate vectors in n-dimensions, they can be used to introduce zeroes selectively. Specifically, given any vector x ~ 0 E R n, one can construct a Householder matrix H such that H x is a multiple of el (the first column of the identity matrix), i.e. make everything except the first row of H x zero. Geometrically, this amounts rotating the vector such that it is parallel to the principal axis. It is easy to see that such H has the form H = I - 2 v v T / v T v where v = x + a e l and a = [[x[[2. In order to avoid subtracting close numbers (while dealing with floating point arithmetic), v is often chosen as v = x + s i g n ( ~ l ) a e l , where ~1 is the first element o f X.
The following function House will compute the vector v, given x, that characterizes H so that H = I - 2 v v T / v T v and that H x = - a e l . Also, v is scaled such t h a t v(1) = 1, as the scaling does not affect H (using a notation similar to MATLAB [5]). To apply H to a vector y, note that
( 2vvTh
Hy =
I-
~-vvJ y = y -
2v( Y) v'v
QR /actorization
vq-y = y - 2-~vV ,
and hence, one can compute H y without explicitly computing H. The same idea can be extended to applying H to a set of columns C E R n x k . Let us call that function row. House(v, C). function: v = House(x) n = length(x); v(1) ----x(1) + sign(x(1)) * norm(x, 2); v ( 2 : n) = x ( 2 : n ) / v ( 1 ) ; v(1) = i; end;
\Vml
Suppose H1 = House(x
Data Loading...
