Basis identification through convex optimization
Is Version Of
Suppose one has a highly redundant spanning set for a
finite-dimensional Hilbert space, knows that a
subset of the spanning set is an orthonormal basis
for the space, and wants to identify that subset.
To identify such a subset, most standard models
typically require that the elements of the spanning set
are arranged in a particular order.
This dissertation develops a novel convex optimization problem,
inspired by compressed sensing, and conjectures that the
set of minimizers to this problem can be used to
identify bases in a given spanning set. In particular,
given an injective matrix X, consider the problem of
minimizing the sum of the absolute values of all entries
in the matrix product XY subject to Y being a left inverse of X.
This dissertation shows that for a given injective
matrix X, the set of such minimizers is a
nonempty, compact, convex set and conjectures that the
extreme points of this set can be used to find a subset
of the rows of X that is a basis for the domain of X.
An analysis of this conjecture is given with particular attention
given to the case when the rows of X are a concatenation
of two orthonormal bases. In this case, it is shown that if a
left inverse Z of X is a minimizer of the sum of the absolute values of
the entries of the matrix product XY subject
to Y being a left inverse of X, and Z identifies an orthonormal
basis in the rows of X, in a way made precise herein,
then Z is an extreme point of
the set of minimizers. Furthermore, conditions are developed that
ensure that such a left inverse Z exists. Last, some special
cases are developed where the above conjecture is shown to hold.