• Deutsch
    • English
  • English 
    • Deutsch
    • English
  • Login
Item View 
  •   Home
  • Naturwissenschaften, Mathematik und Informatik
  • Fakultät für Mathematik und Informatik (inkl. GAUSS)
  • Item View
  •   Home
  • Naturwissenschaften, Mathematik und Informatik
  • Fakultät für Mathematik und Informatik (inkl. GAUSS)
  • Item View
JavaScript is disabled for your browser. Some features of this site may not work without it.

Projection Methods in Sparse and Low Rank Feasibility

by Patrick Neumann
Doctoral thesis
Date of Examination:2015-06-23
Date of issue:2015-07-07
Advisor:Prof. Dr. Russell Luke
Referee:Prof. Dr. Russell Luke
Referee:Prof. Dr. Max Wardetzky
crossref-logoPersistent Address: http://dx.doi.org/10.53846/goediss-5173

 

 

Files in this item

Name:DissertationPatrickNeumann.pdf
Size:2.23Mb
Format:PDF
ViewOpen

The following license files are associated with this item:


Abstract

English

In this thesis, we give an analysis of fixed point algorithms involving projections onto closed, not necessarily convex, subsets of finite dimensional vector spaces. These methods are used in applications such as imaging science, signal processing, and inverse problems. The tools used in the analysis place this work at the intersection of optimization and variational analysis. Based on the underlying optimization problems, this work is devided into two main parts. The first one is the compressed sensing problem. Because the problem is NP-hard, we relax it to a feasibility problem with two sets, namely, the set of vectors with at most s nonzero entries and, for a linear mapping M the affine subspace B of vectors satisfying Mx=p for p given. This problem will be referred to as the sparse-affine-feasibility problem. For the Douglas-Rachford algorithm, we give the proof of linear convergence to a fixed point in the case of a feasibility problem of two affine subspaces. It allows us to conclude a result of local linear convergence of the Douglas-Rachford algorithm in the sparse affine feasibility problem. Proceeding, we name sufficient conditions for the alternating projections algorithm to converge to the intersection of an affine subspace with lower level sets of point symmetric, lower semicontinuous, subadditive functions. This implies convergence of alternating projections to a solution of the sparse affine feasibility problem. Together with a result of local linear convergence of the alternating projections algorithm, this allows us to deduce linear convergence after finitely many steps for any initial point of a sequence of points generated by the alternating projections algorithm. The second part of this dissertation deals with the minimization of the rank of matrices satisfying a set of linear equations. This problem will be called rank-constrained-affine-feasibility problem. The motivation for the analysis of the rank minimization problem comes from the physical application of phase retrieval and a reformulation of the same as a rank minimization problem. We show that, locally, the method of alternating projections must converge at linear rate to a solution of the rank constrained affine feasibility problem.
Keywords: Regularity; Compressed Sensing; Alternating Projections; Douglas-Rachford; Projection Algorithms; Phaselift; Low-Rank Matrices
 

Statistik

Publish here

Browse

All of eDissFaculties & ProgramsIssue DateAuthorAdvisor & RefereeAdvisorRefereeTitlesTypeThis FacultyIssue DateAuthorAdvisor & RefereeAdvisorRefereeTitlesType

Help & Info

Publishing on eDissPDF GuideTerms of ContractFAQ

Contact Us | Impressum | Cookie Consents | Data Protection Information
eDiss Office - SUB Göttingen (Central Library)
Platz der Göttinger Sieben 1
Mo - Fr 10:00 – 12:00 h


Tel.: +49 (0)551 39-27809 (general inquiries)
Tel.: +49 (0)551 39-28655 (open access/parallel publications)
ediss_AT_sub.uni-goettingen.de
[Please replace "_AT_" with the "@" sign when using our email adresses.]
Göttingen State and University Library | Göttingen University
Medicine Library (Doctoral candidates of medicine only)
Robert-Koch-Str. 40
Mon – Fri 8:00 – 24:00 h
Sat - Sun 8:00 – 22:00 h
Holidays 10:00 – 20:00 h
Tel.: +49 551 39-8395 (general inquiries)
Tel.: +49 (0)551 39-28655 (open access/parallel publications)
bbmed_AT_sub.uni-goettingen.de
[Please replace "_AT_" with the "@" sign when using our email adresses.]