Efficient pareto frontier algorithms for computing structured signal representations
Vural, Metin
ℓp-norm minimization plays a significant role in a variety of disciplines. It is not only important for the signal recovery in compressed sensing but also beneficial for finding meaningful signal representations as for the sparse and anti-sparse coding related applications. Therefore, minimizing ℓp-norms in an efficient manner sparked interest in a variety of works. This thesis is concerned with the noise-constrained ℓp-norm minimization for 1 ≤ p ≤ ∞. Although there are various optimization problem formulations that may be used to minimize an ℓp-norm, constraining the noise can offer a more meaningful optimization problem definition since when there is a known noise tolerance in an application, one can simply canalise it into the optimization problem and formulate exactly what to solve. Thus, it is often easier to set the noise tolerance from the optimization perspective. Despite this, there is a lack of computationally efficient algorithms in the literature for the noise-constrained ℓp-norm minimization problem because its feasible area can be complicated. Different optimization problem formulations can provide equivalent solutions and some of them might be easier to solve than the others. Therefore, it might be tempting to solve a computationally efficient problem in order to have the solution to another one. In this thesis, we solved constrained ℓp-norm regularization to reach the solution of the noise-constrained ℓp-norm problem. We introduce optimality tracing based ℓp-norm minimization approaches with simple root finding iterations for 1 ≤ p ≤ ∞. The optimality trade-off between both objectives, the ℓp-norm and a loss function that measures the data misfit, is formulated as a nonlinear equation root finding problem. We present and employ several simple, derivative-free and cost-efficient nonlinear equation root finding methods to trace this optimality over a Pareto frontier. Some of these root finding methods do not require differentiable loss functions and are applicable for both convex and nonconvex data misfits and extend such problems to a broader class of applications. We also introduce a warm-start strategy of taking linear least-squares solution with the one that has minimum ℓ2-norm which is named method of frames (MOF) as an input to require fewer iterations. This warm-start may provide flexible and meaningful starting point initialization for many applications where MOF already exists and can be improved with a better understanding of finitedimensional geometry, e.g. n-widths. The impact of the overcomplete matrix on the convergence rate of some of the presented approaches is demonstrated for matrices fulfilling the Uniform Uncertainty Principle and Uncertainty Principle. These properties were formerly introduced to analyze the performance of random matrices for ℓ1 and ℓ∞-norm related applications respectively. In the last part of the thesis, i.e. in Chapter 7, ℓp-norm minimization related applications are probed with using several loss functions such as least-squares, Huber and a nonconvex penalty Student’s t. ℓ1-norm is minimized with a typical compressed sensing example. Also, a generic test benchmark is utilized for the comparison of the nonlinear equation root finders for ℓ1-norm minimization. A new communication scheme is introduced by minimizing ℓ∞-norm. Outlier detection problem is studied with the minimized ℓ∞-norm, and a prior is offered for the minimized ℓ∞-norm with its performance on peak-to-average power ratio (PAPR). Noise-constrained nuclear norm is minimized as well for the Euclidean distance matrix completion problem with the application of wireless sensor network localization.
Die Minimierung von ℓp-Normen spielt in einer Vielzahl von Disziplinen eine bedeutende Rolle. Sie ist nicht nur wichtig für die Signalwiederherstellung bei der komprimierten Abtastung, sondern auch nützlich, um sinnvolle Signaldarstellungen zu finden, wie für Anwendungen mit geringer und anti-sparse Codierung. Daher hat die effiziente Minimierung von ℓp-Normen das Interesse an einer Vielzahl von Arbeiten geweckt. Diese Dissertation beschäftigt sich mit der rauschbeschränkten ℓp-Normminimierung für 1 ≤ p ≤ ∞. Obwohl es verschiedene Formulierungen von Optimierungsproblemen gibt, die verwendet werden können, um eine ℓp-Norm zu minimieren, kann die Beschränkung des Rauschens eine sinnvollere Definition des Optimierungsproblems bieten. Bei bekannter Rauschtoleranz in einer Anwendung kann man diese in das Optimierungsproblem kanalisieren/integrieren/einbauen und genau formulieren, was/welches Problem zu lösen ist. Daher ist es aus Optimierungssicht oft einfacher, die Rauschtoleranz einzustellen. Trotzdem fehlt es in der Literatur an recheneffizienten Algorithmen für das rauschbeschränkte ℓp-Norm-Minimierungsproblem, da sein zulässiger Bereich kompliziert sein kann. Verschiedene Formulierungen von Optimierungsproblemen können äquivalente Lösungen liefern und einige von ihnen sind möglicherweise einfacher zu lösen als andere. Daher kann es verlockend sein, ein recheneffizientes Problem zu lösen, um die Lösung für ein anderes zu erhalten. In dieser Arbeit wurde die eingeschränkte ℓp-Norm-Regularisierung gelöst, um die Lösung des rauschbeschränkten ℓp-Norm-Problems zu erreichen. Die auf der Optimalitätsverfolgung basierenden ℓp-Norm-Minimierungsansätze mit einfachen Wurzelfindungsiterationen für 1 ≤ p ≤ ∞ werden hierzu vorgestellt. Der Optimalitäts-Trade-off zwischen beiden Zielen, der ℓp-Norm und einer Verlustfunktion, die die Datenfehlanpassung misst, wird als nichtlineares Gleichungswurzelfindungsproblem formuliert. Mehrere einfache, ableitungsfreie und kosteneffiziente Methoden zum Auffinden von nichtlinearen Gleichungswurzeln werden präsentiert und verwendet, um diese Optimalität über eine Pareto-Grenze zu verfolgen. Einige dieser Wurzelfindungsverfahren erfordern keine differenzierbaren Verlustfunktionen und sind sowohl für konvexe als auch für nichtkonvexe Datenfehlanpassungen anwendbar und erweitern solche Probleme auf eine breitere Klasse von Anwendungen. Wir führen auch eine Warmstart-Strategie ein, die eine lineare Lösung der kleinsten Quadrate mit derjenigen mit minimaler ℓ2-Norm, die method of frames (MOF) heißt, als Eingabe verwendet, um weniger Iterationen zu erfordern. Dieser Warmstart kann für viele Anwendungen, bei denen MOF bereits existiert, eine flexible und sinnvolle Startpunktinitialisierung bieten und durch ein besseres Verständnis der endlichdimensionalen Geometrie verbessert werden, z.B. nwidths. Der Einfluss der übervollständigen Matrix auf die Konvergenzrate einiger der vorgestellten Ansätze wird für Matrizen gezeigt, die das Uniform Uncertainty Principle und das Uncertainty Principle erfüllen. Diese Eigenschaften wurden früher eingeführt, um die Leistung von Zufallsmatrizen für ℓ1- bzw. ℓ∞-normbezogene Anwendungen zu analysieren. Im letzten Teil der Arbeit, d. h. in Kapitel 7, werden ℓp-Norm-Minimierungsbezogene Anwendungen mit verschiedenen Verlustfunktionen wie Least-Squares, Huber und einer nichtkonvexen Penalty untersucht Student’s t. ℓ1-norm wird mit einem typischen Compressed-Sensing-Beispiel minimiert. Außerdem wird ein generischer Testbenchmark für den Vergleich der nichtlinearen Gleichungswurzelfinder für die ℓ1-Norm-Minimierung verwendet. Durch Minimierung der ℓ∞-Norm wird ein neues Kommunikationsschema eingeführt. Das Problem der Ausreißererkennung wird mit der minimierten ℓ∞-Norm untersucht und ein Prior wird für die minimierte ℓ∞-Norm mit ihrer Leistung auf peak-to-average power ratio (PAPR) angeboten. Die rauschbeschränkte Nuklearnorm wird auch für das Euklidische Distanzmatrix-Ergänzungsproblem mit der Anwendung der drahtlosen Sensornetzwerklokalisierung minimiert.
