UCLA

We study cases and variants of the following problem: Given a collection of subspaces of a finite-dimensional Euclidean space and a unit vector, iteratively project that vector onto the subspaces in an order determined by a subspace-selection rule. After many iterates, how far away can the final point be from the subspaces? The answer depends on the subspace selection rule. In this dissertation, we study the cyclic rule, in which one cycles over the subspaces, and the greedy rule, in which one always selects a subspace in the collection maximally far from the current position, and some variants. In the cyclic case, we show that if we cycle through 𝑇 subspaces 𝐾 times each, then the average squared distance from the final iterate to the subspaces in the collection is at most 𝑂(𝑇 2/𝐾) by proving a new result of independent interest: For each positive integer 𝑇 , a characterization of which points in the complex plane can lie in the numerical range of the product of 𝑇 (real or complex) projections. Specifically, for each fixed 𝑇 , the set of possible points forms the region bounded by a sinusoidal spiral. In the greedy case, we give a proof that after 𝑘 iterations, the largest possible squared distance from the final iterate to any of the subspaces is 𝑂(𝑘 −1/3 ) via a geometric argument and show that, in the greedy-without-replacement case, no bound on the final average squared distance going to 0 in terms of only 𝑘 exists by constructing examples with large final average squared distance.