This thesis primarily addresses the following problem: why can certain nonconvex optimization problems be solved efficiently? We focus on two important problems in linear algebra and uncover a convexity-like structure that may answer the aforementioned question. This convexity-like structure does not hold in a Euclidean space but rather “geodesically” on a Riemannian manifold. Thus, the main components of this thesis are linear algebra, optimization, and differential geometry. Since it is challenging for a reader to be familiar with all these prerequisites, we strive to present each topic as independently as possible.

The structure analyzed in this thesis facilitates numerous applications in the field of numerical linear algebra. Consequently, a significant portion of the thesis is dedicated to these applications. They include eigenvalue problems in a distributed setting, a new analysis for preconditioned eigenvalue solvers, as well as the development and analysis of new eigenvalue solvers for the most elementary cases. This should certainly be of interest to readers with a background in numerical linear algebra.

On the other hand, readers with an optimization background may view this thesis as an illustration of the importance of the aforementioned structure (weak-quasi-strong convexity). Insights into such structures have appeared not only in linear algebra but also in deep learning. In the final section, we show that this structure is indeed special for optimization in general, as it is in some sense necessary for linear convergence of gradient descent with respect to the error defined by the distances of iterates to the set of optima.

Readers interested in differential geometry may see this thesis as a good example of the power of optimization on Riemannian manifolds. Although differential geometry is not the central focus of this thesis, all the structures discussed hold over curved spaces. This serves as an excellent example of the primary goal of optimization on Riemannian manifolds: solving typically non-convex problems within geometries where they satisfy a certain convexity structure.