Algorithms and theory for clustering and nonconvex quadratic programming
Abstract/Contents
- Abstract
- In this dissertation we discuss three problems characterized by hidden structure or information. The first part of this thesis focuses on extracting subspace structures from data. Subspace Clustering is the problem of finding a multi-subspace representation that best fits a collection of points taken from a high-dimensional space. As with most clustering problems, popular techniques for subspace clustering are often difficult to analyze theoretically and/or terminate in local optima of non-convex functions--these problems are only exacerbated in the presence of noise and missing data. We introduce a collection of subspace clustering algorithms, which are tractable and provably robust to various forms of data imperfections. We further illustrate our methods with numerical experiments on a wide variety of data segmentation problems. In the second part of the thesis, we consider the problem of recovering the seemingly hidden phase of an object from intensity-only measurements, a problem which naturally appears in X-ray crystallography and related disciplines. We formulate the problem as a non-convex quadratic program whose global optimum recovers the phase information exactly from a near minimal number of magnitude-only measurements. To solve this non-convex problem, we develop an iterative algorithm that starts with a careful initialization and then refines this initial estimate by iteratively applying novel update rules. The main contribution is that we show that the sequence of successive iterates provably converges to the global optimum at a geometric rate so that the proposed scheme is efficient both in terms of computational and data resources. We also show that this approach is stable vis a vis noise. In theory, a variation on this scheme leads to a near-linear time algorithm for a physically realizable model based on coded diffraction patterns. In this part of the thesis we also prove similar results about two other approaches, the first one is based on convex optimization and the second one is inspired by the error reduction algorithm of Gerchberg-Saxton and Fienup. We illustrate the effectiveness of our methods with various experiments on image data. Underlying the analysis of this part of the thesis are insights for the analysis of non-convex optimization schemes that may have implications for computational problems beyond phase retrieval. In the third part of the thesis, we look at two related problems involving coherent and redundant dictionaries. The first problem, is about the recovery of signals from under-sampled data in the common situation where such signals are not sparse in an orthonormal basis, but in a coherent and redundant dictionary. We focus on a formulation of the problem where one minimizes the $\ell_1$ norm of the coefficients of the representation of the signal in the dictionary subject to the measurement constraints, a.k.a. the synthesis problem. For this formulation we characterize the required number of random measurements in terms of geometric quantities related to the dictionary. Furthermore, we connect this problem to the denoising problem where instead of under-sampled measurements of the signal we observe a noisy version of it. In this case we characterize the reconstruction error obtained by using the over-complete dictionary for denoising and show that it depends on the same geometric quantities that affect the number of measurements in the synthesis problem. The second problem concerns sparse recovery with coherent and redundant dictionaries which appears in a variety of applications such as microscopy, astronomy, tomography, computer vision, radar, and seismology. Our results show that sparse recovery via $\ell_1$ minimization is effective in these dictionaries even though these dictionaries have maximum pair-wise column coherence very close to 1, i.e. they contain almost identical columns. This holds with the proviso that the sparse coefficients are not too clustered. This general theory, when applied to the special case of low pass Fourier (a.k.a. super-resolution), allows for less restrictive requirements when compared with recent literature with significantly shorter proofs.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2014 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Soltanolkotabi, Mahdi |
|---|---|
| Associated with | Stanford University, Department of Electrical Engineering. |
| Primary advisor | Candès, Emmanuel J. (Emmanuel Jean) |
| Thesis advisor | Candès, Emmanuel J. (Emmanuel Jean) |
| Thesis advisor | Hastie, Trevor |
| Thesis advisor | Montanari, Andrea |
| Advisor | Hastie, Trevor |
| Advisor | Montanari, Andrea |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Mahdi Soltanolkotabi. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2014. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2014 by Mahdi Soltanolkotabi
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...