Optimal linear combinations using householder transformations

In pattern classification of sampled vector valued random variables it is often essential, due to computational and accuracy considerations, to consider certain measurable transformations of the random variable. These transformations are generally of a dimension-reducing nature. In this paper we consider the class of linear dimension reducing transformations, i.e., the k × n matrices of rank k where k < n and n is the dimension of the range of the sampled vector random variable.

In this connection, we use certain results (Decell and Quirein, 1973), that guarantee, relative to various class separability criteria, the existence of an extremal transformation. These results also guarantee that the extremal transformation can be expressed in the form (I_k∣ Z)U where I_k is the k × k identity matrix and U is an orthogonal n × n matrix. These results actually limit the search for the extremal linear transformation to a search over the obviously smaller class of k × n matrices of the form (I_k ∣Z)U. In this paper these results are refined in the sense that any extremal transformation can be expressed in the form (I_K∣Z)H_p … H₁ where p ≤ min{k, n?k} and H_i is a Householder transformation i=l,…, p, The latter result allows one to construct a sequence of transformations (L_K∣ Z)H₁, (I_K Z)H₂H₁ … such that the values of the class separability criterion evaluated at this sequence is a bounded, monotone sequence of real numbers. The construction of the i-th element of the sequence of transformations requires the solution of an n-dimensional optimization problem. The solution, for various class separability criteria, of the optimization problem will be the subject of later papers. We have conjectured (with supporting theorems and empirical results) that, since the bounded monotone sequence of real class separability values converges to its least upper bound, this least upper bound is an extremal value of the class separability criterion.

Several open questions are stated and the practical implications of the results are discussed.