Constructing Accelerated Algorithms for Large-scale Optimization - Framework, Algorithms, and Applications

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorFlorea, Mihai Iulian
dc.contributor.departmentSignaalinkäsittelyn ja akustiikan laitosfi
dc.contributor.departmentDepartment of Signal Processing and Acousticsen
dc.contributor.labSignal Processing Groupen
dc.contributor.schoolSähkötekniikan korkeakoulufi
dc.contributor.schoolSchool of Electrical Engineeringen
dc.contributor.supervisorVorobyov, Sergiy A., Prof., Aalto University, Department of Signal Processing and Acoustics, Finland
dc.date.accessioned2018-11-20T10:03:21Z
dc.date.available2018-11-20T10:03:21Z
dc.date.defence2018-10-23
dc.date.issued2018
dc.description.abstractA wide range of inverse problems and various machine learning tasks can be expressed as large-scale optimization problems with a composite objective structure, where the gradient of the smooth part has a global Lipschitz constant that is either impractical to compute, or considerably larger than the local values. The smooth part may be strongly convex as well, especially in certain medical imaging applications. The only fast methods that are able to address this entire class of problems are similar to or based on the black-box algorithms developed and analyzed by Nesterov using the estimate sequence mathematical framework. In this work, we introduce the augmented estimate sequence framework, a relaxation of the estimate sequence. When the lower bounds incorporated in the augmented estimate functions are hyperplanes or parabolae, this framework generates a conceptually simple gap sequence. We use this gap sequence to construct the Accelerated Composite Gradient Method (ACGM), a versatile first-order scheme applicable to the entire composite problem class. ACGM is endowed with an efficient dynamic Lipschitz constant estimation (line-search) procedure and features monotonicity. Motivated by the absence of an accurate complexity measure applicable to all first-order methods, we also introduce the wall-clock time unit (WTU). The WTU accounts for variations in algorithmic per-iteration complexity and more consistently reflects the performance of first-order methods in practice. When analyzed using WTU, ACGM has the best provable convergence rate on the composite problem class, both in the strongly and non-strongly convex cases. We confirm the superiority of ACGM within its class using an extensive simulation benchmark. ACGM also excels in terms of robustness and usability. In particular, ACGM is guaranteed to converge without requiring any quantitative prior information. Additional information, if available, leads to an improvement in performance at least on par with competing methods. Moreover, ACGM actually encompasses several popular algorithms for large-scale optimization, including Nesterov's Fast Gradient Method (FGM) and the Fast Iterative Shrinkage Thresholding Algorithm (FISTA), along with their most common variants. The efficiency and generality of ACGM enables new applications, particularly in ultrasound image reconstruction. In contrast with the unrealistic models of existing approaches, we propose two ultrasound image formation models based on spatially varying kernel convolution that account for arbitrary boundary conditions. We provide these models and their adjoints with resource efficient matrix-free implementations. Using either of our models, a variant of ACGM optimized for this task is able to efficiently reconstruct large ultrasound images with accuracy vastly superior to the state-of-the-art.en
dc.format.extent147 + app. 61
dc.format.mimetypeapplication/pdfen
dc.identifier.isbn978-952-60-8227-1 (electronic)
dc.identifier.isbn978-952-60-8226-4 (printed)
dc.identifier.issn1799-4942 (electronic)
dc.identifier.issn1799-4934 (printed)
dc.identifier.issn1799-4934 (ISSN-L)
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/34796
dc.identifier.urnURN:ISBN:978-952-60-8227-1
dc.language.isoenen
dc.opnNesterov, Yurii, Prof., Catholic University of Louvain, Belgium
dc.opnPesquet, Jean-Christophe, Prof., University of Paris-Saclay, France
dc.publisherAalto Universityen
dc.publisherAalto-yliopistofi
dc.relation.haspart[Publication 1]: Mihai I. Florea, Sergiy A. Vorobyov. A Robust FISTA-like Algorithm. In IEEE International Conference on Acoustics, Speech and Signal Processing, New Orleans, USA, pp. 4521–4525, Mar. 2017. DOI: 10.1109/ICASSP.2017.7953012
dc.relation.haspart[Publication 2]: Mihai I. Florea, Sergiy A. Vorobyov. An Accelerated Composite Gradient Method for Large-scale Composite Objective Problems. Accepted for publication in IEEE Transactions on Signal Processing, May 2018.
dc.relation.haspart[Publication 3]: Mihai I. Florea, Sergiy A. Vorobyov. A Generalized Accelerated Composite Gradient Method: Uniting Nesterov’s Fast Gradient Method and FISTA. Submitted to IEEE Transactions on Signal Processing, Oct. 2018.
dc.relation.haspart[Publication 4]: Mihai I. Florea, Adrian Basarab, Denis Kouamé, Sergiy A. Vorobyov. Restoration of Ultrasound Images using Spatially-variant Kernel Deconvolution. In IEEE International Conference on Acoustics, Speech and Signal Processing, Calgary, Canada, pp. 796–800, Apr. 2018.
dc.relation.haspart[Publication 5]: Mihai I. Florea, Adrian Basarab, Denis Kouamé, Sergiy A. Vorobyov. An Axially Variant Kernel Imaging Model Applied to Ultrasound Image Reconstruction. IEEE Signal Processing Letters, vol. 25, no.7, pp. 961–965, Jul. 2018. DOI: 10.1109/LSP.2018.2824764
dc.relation.ispartofseriesAalto University publication series DOCTORAL DISSERTATIONSen
dc.relation.ispartofseries197/2018
dc.revNesterov, Yurii, Prof., Catholic University of Louvain, Belgium
dc.revBioucas Dias, José M., Prof., University of Lisbon, Portugal
dc.subject.keywordaccelerationen
dc.subject.keywordcomposite objectiveen
dc.subject.keywordestimate sequenceen
dc.subject.keywordfast gradient methoden
dc.subject.keywordfirst-order methoden
dc.subject.keywordFISTAen
dc.subject.keywordlarge-scale optimizationen
dc.subject.keywordline-searchen
dc.subject.otherElectrical engineeringen
dc.titleConstructing Accelerated Algorithms for Large-scale Optimization - Framework, Algorithms, and Applicationsen
dc.typeG5 Artikkeliväitöskirjafi
dc.type.dcmitypetexten
dc.type.ontasotDoctoral dissertation (article-based)en
dc.type.ontasotVäitöskirja (artikkeli)fi
local.aalto.acrisexportstatuschecked
local.aalto.archiveyes
local.aalto.formfolder2018_11_20_klo_10_05

Files

Original bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
isbn9789526082271.pdf
Size:
3.69 MB
Format:
Adobe Portable Document Format
Description: