| 1. |
- Lindbäck, Jacob, 1995-
(författare)
-
Novel Algorithms for Optimal Transport via Splitting Methods
- 2023
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis studies how the Douglas–Rachford splitting technique can be leveraged for scalable computational optimal transport (OT). By carefully splitting the problem, we derive an algorithm with several advantages. First, the algorithm enjoys global convergence rates comparable to the state-of-the-art while benefiting from accelerated local rates. In contrast to other methods, it does not depend on hyperparameters that can cause numerical instability. This feature is particularly advantageous when low-precision floating points are used or if the data is noisy. Moreover, the updates can efficiently be carried out on GPUs and, therefore, benefit from the high degree of parallelization achieved via GPU computations. Furthermore, we show that the algorithm can be extended to handle a broad family of regularizers and constraints while enjoying the same theoretical and numerical properties. These factors combined result in a fast algorithm that can be applied to large-scale OT problems and regularized versions thereof, which we illustrate in several numerical experiments.In the first part of the main body of the thesis, we present how Douglas-Rachford splitting can be adapted for the unregularized OT problem to derive a fast algorithm. We present two global convergence guarantees for the resulting algorithm: a 1/k-ergodic rate and a linear rate. We also show that the stopping criteria of the algorithm can be computed on the fly with virtually no extra costs. Further, we specify how a GPU kernel can be efficiently implemented to carry out the operations needed for the algorithm. To show that the algorithm is fast, accurate, and robust, we run a series of numerical benchmarks that demonstrate the advantages of our algorithm. We then extend the algorithm to handle regularized OT using sparsity-promoting regularizers. The generalized algorithm will enjoy the same sublinear rate derived for the unregularized formulation. We also complement the global rate with local guarantees, establishing that, under non-degeneracy assumptions on the solution, the algorithm will identify the correct sparsity pattern of the solution in finitely many iterations. When the sparsity pattern is identified, a faster linear rate typically dominates. We also specify how to extend to the GPU implementation and the stopping criteria to handle regularized OT, and we subsequently specify how to backpropagate through the solver. We end this part of the thesis by presenting some numerical results, including performance on quadratically regularized OT and group Lasso regularized OT for domain adaptation, showing a substantial improvement compared to the state-of-the-art.In the last part of the thesis, we provide a more detailed analysis of the local behavior of the algorithm when applied to unregularized OT and quadratically regularized OT. We subsequently outline how to extend this analysis to several other sparsity-promoting regularizers. In the former two cases, we show that the update that constitutes the algorithm converges to a linear operator in finitely many iterations. By analyzing the spectral properties of these linear operators, we gain insights into the local behavior of the algorithm, and specifically, these results suggest how to tune stepsizes to obtain better local rates.
|
|
| 2. |
- Touqir Pasha, Muhammad
(författare)
-
Circuit Design for All-Digital Frequency Synthesizers
- 2014
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The market for low cost portable electronics is rapidly growing. Physical activity monitors, portable music players, and smart watches are fast becoming a part of daily life. As the market for wearable devices has grown, a primary concern for IC manufacturers is to provide low cost, low power and lightweight circuit solutions. In a bid to lower the costs and extend battery life there is an increased interest in using low-cost, low-power CMOS processes. As a result fully integrated systems on chips (SOC) have been realized that efficiently perform the required functions. These SOCs house digital, analog and in some cases radio circuits on a single die in a bid to reduce cost and improve productivity.Phase Locked Loops (PLLs) are a key building block for all SOCs where they are used to generate clock signals for synchronous systems. In monolithic implementations the design cost of a circuit is measured in terms of the silicon area and not the number of devices in the circuit. With the advent of all-digital techniques, there is a renewed interest in the design of compact PLLs as the area occupied by the traditional PLLs is very large due to the presence of large passive components in the loop filter and the oscillator. As a result, various digital circuit design techniques are being explored to design compact all-digital PLLs (ADPLLs) while satisfying the performance requirements for the target applications.The focus of this work is to explore new techniques for area, power and time efficient design of ADPLL component blocks. The first part of this works focuses on the feasibility of using automatic place and route (P&R) tools to synthesize a time-to-digital converter (TDC). An area efficient TDC is synthesized in a 65 nm CMOS process using automated P&R which exhibits a time resolution of 6.5 ps with an input sampling rate of 100 MS/s while occupying an area of 0.002 mm2. A modified switching scheme is also presented which reduces the power consumption of the thermometer-to-binary encoder by up to 40%.The second part of this thesis proposes a power supply filter for mitigating the affect of cyclostationary noise on the voltage controlled ring oscillator. The key idea is to raise the impedance in the current supply during the sensitive periods and lower it during insensitive periods of the oscillator operation. To demonstrate the feasibility of the proposed filter, a pseudo differential ring oscillator is designed in a 65 nm CMOS process which exhibits an rms jitter of less than 14 ps at 2.4 GHz in the presence of a 500 mV noise tone in the power supply.
|
|
