CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Multidimensional inverse problems in imaging and identification using low-complexity models, optimal mass transport, and machine learning
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.ORCID iD: 0000-0002-9778-1426
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis, which mainly consists of six appended papers, primarily considers a number of inverse problems in imaging and system identification.

In particular, the first two papers generalize results for the rational covariance extension problem from one to higher dimensions. The rational covariance extension problem stems from system identification and can be formulated as a trigonometric moment problem, but with a complexity constraint on the sought measure. The papers investigate a solution method based on varia tional regularization and convex optimization. We prove the existence and uniqueness of a solution to the variational problem, both when enforcing exact moment matching and when considering two different versions of approximate moment matching. A number of related questions are also considered, such as well-posedness, and the theory is illustrated with a number of examples.

The third paper considers the maximum delay margin problem in robust control: To find the largest time delay in a feedback loop for a linear dynamical system so that there still exists a single controller that stabilizes the system for all delays smaller than or equal to this time delay. A sufficient condition for robust stabilization is recast as an analytic interpolation problem, which leads to an algorithm for computing a lower bound on the maximum delay margin. The algorithm is based on bisection, where positive semi-definiteness of a Pick matrix is used as selection criteria.

Paper four investigate the use of optimal transport as a regularizing functional to incorporate prior information in variational formulations for image reconstruction. This is done by observing that the so-called Sinkhorn iterations, which are used to solve large scale optimal transport problems, can be seen as coordinate ascent in a dual optimization problem. Using this, we extend the idea of Sinkhorn iterations and derive a iterative algorithm for computing the proximal operator. This allows us to solve large-scale convex optimization problems that include an optimal transport term.

In paper five, optimal transport is used as a loss function in machine learning for inverse problems in imaging. This is motivated by noise in the training data which has a geometrical characteristic. We derive theoretical results that indicate that optimal transport is better at compensating for this type of noise, compared to the standard 2-norm, and the effect is demonstrated in a numerical experiment.

The sixth paper considers using machine learning techniques for solving large-scale convex optimization problems. We first parametrizes a family of algorithms, from which a new optimization algorithm is derived. Then we apply machine learning techniques to learn optimal parameters for given families of optimization problems, while imposing a fixed number of iterations in the scheme. By constraining the parameters appropriately, this gives learned optimization algorithms with provable convergence.

Abstract [sv]

Denna avhandling, som huvudsakligen består av de sex bifogade artiklarna, berör ett antal olika inversa problem med tillämpning inom bildrekonstruktion och systemidentifiering.

The två första artiklarna generaliserar resultat från litteraturen gällande det rationella kovariansutvidgningsproblemet, från det en-dimensionella fallet till det fler-dimensionella fallet. Det rationella kovariansutvidgningsproblemet har sitt ursprung inom systemidentifiering och kan formuleras som ett trigonometriska momentproblem. Momentproblemet är dock av icke-klassisk karaktär, eftersom det sökta måttet har ett bivillkor som begränsar dess komplexitet. Papperna undersöker olika metoder för att lösa problemet, metoder som alla bygger på variationell regularisering och konvex optimering. Vi undersöker både exakt och approximativ kovariansmatchning, och huvudresultaten är bevis av existens och unikhet vad gäller lösning till dessa olika problem. Artiklarna undersöker även ett antal relaterade frågor, så som välställdhet av problemen, och teorin är också illustrerad med ett antal olika exempel och tillämpningar.

Det tredje pappret behandlar ett problem inom robust reglering för linjära system: ett systems tidsfördröjningsmarginal. Tidsfördröjningsmarginalen är den längsta tidsfördröjning ett återkopplat linjärt dynamiskt system kan ha så att det fortfarande finns en enda regulator som stabiliserar systemet för alla tidsfördröjningar som är kortare. Artikeln undersöker ett tillräckligt villkor, och formulerar om detta som ett analytiskt interpolationsproblem. Detta leder till en algoritm för att beräkna en undre gräns för tidsfördröjningsmarginalen. Algoritmen bygger på intervallhalveringsmetoden, och använder Pick-matrisens teckenkaraktär som urvalskriterium.

Artikel fyra undersöker användandet av optimal masstransport som regulariseringsfunktion vid bildrekonstruktion. Idén är att använda optimal masstransport som ett avstånd mellan bilder, och på så vis kunna inkorporera förhandsinformation i rekonstruktionen. Mer specifikt görs detta genom att utvidga de så kallade Sinkhorn-iterationerna, som används för att beräkna lösningen till optimal masstransportsproblemet. Vi åstadkommer denna utvidgning genom att observera att Sinkhorn-iterationerna är ekvivalent med koordinatvis optimering i ett dualt problem. Med hjälp av detta tar vi fram en algoritm för att beräkna proximal-operatorn till optimal masstransportproblemet, vilket gör att vi kan lösa storskaliga optimeringsproblem som innehåller en sådan term.

I femte artikeln använder vi istället optimal masstransport som kostnadsfunktion vid träning av neurala nätverk för att lösa inversa problem inom bildrekonstruktion. Detta motiveras genom tillämpningar där bruset i data är av geometrisk karaktär. Vi presenterar teoretiska resultat som indikerar att optimal masstransport är bättre på att kompensera för denna typ av brus än till exempel 2-normen. Denna effekt demonstreras också i ett numerisk experiment.

Det sjätte pappret undersöker användandet av maskininlärning för att lösa storskaliga optimeringsproblem. Detta görs genom att först parametrisera en familj av algoritmer, ur vilken vi också härleder en ny optimeringsmetod. Vi använder sedan maskininlärning för att ta fram optimala parametrar i denna familj av algoritmer, givet en viss familj av optimeringsproblem samt givet att bara ett fixt antal iterationer får göras i lösningsmetoden. Genom att begränsa sökrymden för algoritmparametrarna kan vi också garantera att den inlärda metoden är en konvergent optimeringsalgoritm.

Place, publisher, year, edition, pages
Stockholm, Sweden: KTH Royal Institute of Technology, 2018. , p. 60
Series
TRITA-SCI-FOU ; 2018:53
Keywords [en]
Inverse problems, convex optimization, variational regularization, trigonometric moment problems, optimal mass transport, computed tomography, machine learning, analytic interpolation, delay systems
Keywords [sv]
Inversa problem, konvex optimering, variationell regularisering, trigonometriska momentproblem, optimal masstransport, datortomografi, maskininlärning, analytisk interpolation, system med tidsfördröjning
National Category
Computational Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-239726ISBN: 978-91-7873-050-6 (print)OAI: oai:DiVA.org:kth-239726DiVA, id: diva2:1267251
Public defence
2019-01-17, F3, Lindstedtsvägen 26, Stockholm, 13:00 (English)
Opponent
Supervisors
Note

QC 20181204

Available from: 2018-12-04 Created: 2018-11-30 Last updated: 2018-12-04Bibliographically approved
List of papers
1. Multidimensional rational covariance extension
Open this publication in new window or tab >>Multidimensional rational covariance extension
(English)Manuscript (preprint) (Other academic)
Abstract [en]

The rational covariance extension problem (RCEP) is an important problem in systems and control occurring in such diverse fields as control, estimation, system identification, and signal and image processing, leading to many fundamental theoretical questions. In fact, this inverse problem is a key component in many identification and signal processing techniques and plays a fundamental role in prediction, analysis, and modeling of systems and signals. It is well-known that the RCEP can be reformulated as a (truncated) trigonometric moment problem subject to a rationality condition. In this paper we consider the more general multidimensional trigonometric moment problem with a similar rationality constraint. This generalization creates many interesting new mathematical questions and also provides new insights into the original one-dimensional problem. A key concept in this approach is the complete smooth parametrization of all solutions, allowing solutions to be tuned to satisfy additional design specifications without violating the complexity constraints. As an illustration of the potential of this approach we apply our results to multidimensional spectral estimation, Wiener system identification, and image compression.

Keywords
Covariance extension, trigonometric moment problem, convex optimization, generalized entropy, multidimensional spectral estimation, system identification, image compression
National Category
Computational Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kth:diva-239874 (URN)
Note

QC 20181204

Available from: 2018-12-03 Created: 2018-12-03 Last updated: 2018-12-04Bibliographically approved
2. Multidimensional rational covariance extension with approximate covariance matching
Open this publication in new window or tab >>Multidimensional rational covariance extension with approximate covariance matching
2018 (English)In: SIAM Journal of Control and Optimization, ISSN 0363-0129, E-ISSN 1095-7138, Vol. 56, no 2, p. 913-944Article in journal (Refereed) Published
Abstract [en]

In our companion paper [A. Ringh, J. Karlsson, and A. Lindquist, SIAM T. Control Opton., 54 (2016), pp. 1950-1982] we discussed the multidimensional rational covariance extension problem (RCEP), which has important applications in image processing and spectral estimation in radar, sonar, and medical imaging. This is an inverse problem where a power spectrum with a rational absolutely continuous part is reconstructed from a finite set of moments. However, in most applications these moments are determined from observed data and are therefore only approximate, and the RCEP may not have a solution. In this paper we extend the results of our companion paper to handle approximate covariance matching. We consider two problems, one with a soft constraint and the other one with a hard constraint, and show that they are connected via a homeomorphism. We also demonstrate that the problems are well-posed and illustrate the theory by examples in spectral estimation and texture generation.

Place, publisher, year, edition, pages
Society for Industrial and Applied Mathematics Publications, 2018
Keywords
Convex optimization, Covariance extension, Generalized entropy, Multidimensional spectral estimation, Trigonometric moment problem, Estimation, Signal processing, Spectrum analysis, Generalized entropies, Moment problems, Rational covariance extension problem, Signal processing technique, Spectral Estimation, Inverse problems, Texture generation
National Category
Mathematics Signal Processing
Identifiers
urn:nbn:se:kth:diva-233813 (URN)10.1137/17M1127922 (DOI)000429992600014 ()2-s2.0-85046695922 (Scopus ID)
Funder
Swedish Research Council, 2014-5870Swedish Foundation for Strategic Research , AM13-0049
Note

QC 20180829

Available from: 2018-08-29 Created: 2018-08-29 Last updated: 2018-11-30Bibliographically approved
3. Lower bounds on the maximum delay margin by analytic interpolation
Open this publication in new window or tab >>Lower bounds on the maximum delay margin by analytic interpolation
2018 (English)In: 2018 IEEE 57th Annual Conference on Decision and Control (CDC), 2018Conference paper, Published paper (Refereed)
Abstract [en]

We study the delay margin problem in the context of recent works by T. Qi, J. Zhu, and J. Chen, where a sufficient condition for the maximal delay margin is formulated in terms of an interpolation problem obtained after introducing a rational approximation. Instead we omit the approximation step and solve the same problem directly using techniques from function theory and analytic interpolation. Furthermore, we introduce a constant shift in the domain of the interpolation problem. In this way we are able to improve on their lower bound for the maximum delay margin.

Series
IEEEConference on Decision and Control
National Category
Control Engineering Other Mathematics
Identifiers
urn:nbn:se:kth:diva-239720 (URN)
Conference
IEEE 57th Annual Conference on Decision and Control (CDC),Miami Beach, FL, USA, December 17-19, 2018
Funder
Swedish Research Council, 2014-5870
Note

QC 20181214

Available from: 2018-11-30 Created: 2018-11-30 Last updated: 2018-12-14Bibliographically approved
4. Generalized Sinkhorn Iterations for Regularizing Inverse Problems Using Optimal Mass Transport
Open this publication in new window or tab >>Generalized Sinkhorn Iterations for Regularizing Inverse Problems Using Optimal Mass Transport
2017 (English)In: SIAM Journal on Imaging Sciences, ISSN 1936-4954, E-ISSN 1936-4954, Vol. 10, no 4, p. 1935-1962Article in journal (Refereed) Published
Abstract [en]

The optimal mass transport problem gives a geometric framework for optimal allocation and has recently attracted significant interest in application areas such as signal processing, image processing, and computer vision. Even though it can be formulated as a linear programming problem, it is in many cases intractable for large problems due to the vast number of variables. A recent development addressing this builds on an approximation with an entropic barrier term and solves the resulting optimization problem using Sinkhorn iterations. In this work we extend this methodology to a class of inverse problems. In particular we show that Sinkhorn-type iterations can be used to compute the proximal operator of the transport problem for large problems. A splitting framework is then used to solve inverse problems where the optimal mass transport cost is used for incorporating a priori information. We illustrate this method on problems in computerized tomography. In particular we consider a limited-angle computerized tomography problem, where a priori information is used to compensate for missing measurements.

Place, publisher, year, edition, pages
Society for Industrial and Applied Mathematics, 2017
Keywords
inverse problems, optimal mass transport, Sinkhorn iterations, proximal methods, variable split- ting, medical imaging
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kth:diva-219364 (URN)10.1137/17M111208X (DOI)000418654000009 ()2-s2.0-85039745826 (Scopus ID)
Funder
Swedish Research Council, 2014-5870Swedish Foundation for Strategic Research , AM13-0049
Note

QC 20171212

Available from: 2017-12-04 Created: 2017-12-04 Last updated: 2018-11-30Bibliographically approved
5. Learning to solve inverse problems using Wasserstein loss
Open this publication in new window or tab >>Learning to solve inverse problems using Wasserstein loss
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We propose using the Wasserstein loss for training in inverse problems. In particular, we consider a learned primal-dual reconstruction scheme for ill-posed inverse problems using the Wasserstein distance as loss function in the learning. This is motivated by miss-alignments in training data, which when using standard mean squared error loss could severely degrade reconstruction quality. We prove that training with the Wasserstein loss gives a reconstruction operator that correctly compensates for miss-alignments in certain cases, whereas training with the mean squared error gives a smeared reconstruction. Moreover, we demonstrate these effects by training a reconstruction algorithm using both mean squared error and optimal transport loss for a problem in computerized tomography.

National Category
Computational Mathematics Signal Processing Medical Image Processing Probability Theory and Statistics
Research subject
Mathematics; Applied and Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-239723 (URN)
Funder
Swedish Foundation for Strategic Research , AM13- 0049Swedish Foundation for Strategic Research , ID14-0055Swedish Research Council, 2014-5870
Note

QC 20181211

Available from: 2018-11-30 Created: 2018-11-30 Last updated: 2018-12-11Bibliographically approved
6. Data-driven nonsmooth optimization
Open this publication in new window or tab >>Data-driven nonsmooth optimization
Show others...
(English)Manuscript (preprint) (Other academic)
National Category
Computational Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kth:diva-229649 (URN)
Note

QC 20180611

Available from: 2018-06-05 Created: 2018-06-05 Last updated: 2018-11-30Bibliographically approved

Open Access in DiVA

AxelRingh_Thesis(1059 kB)16 downloads
File information
File name FULLTEXT01.pdfFile size 1059 kBChecksum SHA-512
1bb5426d0bcc8abf88c53e50ab1517146eb70ae94c87311549e6182809d4d4a4596770440a54280b6e6bb3959f430a95ce460d16580e8513eef900617c54b533
Type fulltextMimetype application/pdf

Authority records BETA

Ringh, Axel

Search in DiVA

By author/editor
Ringh, Axel
By organisation
Optimization and Systems Theory
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 16 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 130 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf