We propose a dynamic, input dependent filter approximation and selection technique to improve the computational efficiency of Deep Neural Networks. The approximation techniques convert 32 bit floating point representation of filter weights in neural networks into smaller precision values. This is done by reducing the number of bits used to represent the weights. In order to calculate the per-input error between the trained full precision filter weights and the approximated weights, a metric called Multiplication Error (ME) has been chosen. For convolutional layers, ME is calculated by subtracting the approximated filter weights from the original filter weights, convolving the difference with the input and calculating the grand-sum of the resulting matrix. For fully connected layers, ME is calculated by subtracting the approximated filter weights from the original filter weights, performing matrix multiplication between the difference and the input and calculating the grand-sum of the resulting matrix. ME is computed to identify approximated filters in a layer that result in low inference accuracy. In order to maintain the accuracy of the network, these filters weights are replaced with the original full precision weights. Prior work has primarily focused on input independent (static) replacement of filters to low precision weights. In this technique, all the filter weights in the network are replaced by approximated filter weights. This results in a decrease in inference accuracy. The decrease in accuracy is higher for more aggressive approximation techniques. Our proposed technique aims to achieve higher inference accuracy by not approximating filters that generate high ME. Using the proposed per-input filter selection technique, LeNet achieves an accuracy of 95.6% with 3.34% drop from the original accuracy value of 98.9% for truncating to 3 bits for the MNIST dataset. On the other hand upon static filter approximation, LeNet achieves an accuracy of 90.5% with 8.5% drop from the original accuracy. The aim of our research is to potentially use low precision weights in deep learning algorithms to achieve high classification accuracy with less computational overhead. We explore various filter approximation techniques and implement a per-input filter selection and approximation technique that selects the filters to approximate during run-time. / Master of Science / Deep neural networks, just like the human brain can learn important information about the data provided to them and can classify a new input based on the labels corresponding to the provided dataset. Deep learning technology is heavily employed in devices using computer vision, image and video processing and voice detection. The computational overhead incurred in the classification process of DNNs prohibits their use in smaller devices. This research aims to improve network efficiency in deep learning by replacing 32 bit weights in neural networks with less precision weights in an input-dependent manner. Trained neural networks are numerically robust. Different layers develop tolerance to minor variations in network parameters. Therefore, differences induced by low-precision calculations fall well within tolerance limit of the network. However, for aggressive approximation techniques like truncating to 3 and 2 bits, inference accuracy drops severely. We propose a dynamic technique that during run-time, identifies the approximated filters resulting in low inference accuracy for a given input and replaces those filters with the original filters to achieve high inference accuracy. The proposed technique has been tested for image classification on Convolutional Neural Networks. The datasets used are MNIST and CIFAR-10. The Convolutional Neural Networks used are 4-layered CNN, LeNet-5 and AlexNet.

In this thesis, we will show how certain classes of quantum many-body Hamiltonians with $\su{2}_1 \oplus \su{2}_2 \oplus \ldots \oplus \su{2}_k$ spectrum generating algebras can be approximated by multi-dimensional shifted harmonic oscillator Hamiltonians. The dimensions of the Hilbert spaces of such Hamiltonians usually depend exponentially on $k$. This can make obtaining eigenvalues by diagonalization computationally challenging. The Shifted Harmonic Approximation (SHA) developed here gives good predictions of properties such as ground state energies, excitation energies and the most probable states in the lowest eigenstates. This is achieved by solving only a system of $k$ equations and diagonalizing $k\times k$ matrices. The SHA gives accurate approximations over wide domains of parameters and in many cases even across phase transitions. The SHA is first illustrated using the Lipkin-Meshkov-Glick (LMG) model and the Canonical Josephson Hamiltonian (CJH) which have $\su{2}$ spectrum generating algebras. Next, we extend the technique to the non-compact $\su{1,1}$ algebra, using the five-dimensional quartic oscillator (5DQO) as an example. Finally, the SHA is applied to a $k$-level Bardeen-Cooper-Shrieffer (BCS) pairing Hamiltonian with fixed particle number. The BCS model has a $\su{2}_1 \oplus \su{2}_2 \oplus \ldots \oplus \su{2}_k$ spectrum generating algebra. An attractive feature of the SHA is that it also provides information to construct basis states which yield very accurate eigenvalues for low-lying states by diagonalizing Hamiltonians in small subspaces of huge Hilbert spaces. For Hamiltonians that involve a smaller number of operators, accurate eigenvalues can be obtained using another technique developed in this thesis: the generalized Rowe-Rosensteel-Kerman-Klein equations-of-motion method (RRKK). The RRKK is illustrated using the LMG and the 5DQO. In RRKK, solving unknowns in a set of $10\times 10$ matrices typically gives estimates of the lowest few eigenvalues to an accuracy of at least eight significant figures. The RRKK involves optimization routines which require initial guesses of the matrix representations of the operators. In many cases, very good initial guesses can be obtained using the SHA. The thesis concludes by exploring possible future developments of the SHA.

In this thesis, we will show how certain classes of quantum many-body Hamiltonians with $\su{2}_1 \oplus \su{2}_2 \oplus \ldots \oplus \su{2}_k$ spectrum generating algebras can be approximated by multi-dimensional shifted harmonic oscillator Hamiltonians. The dimensions of the Hilbert spaces of such Hamiltonians usually depend exponentially on $k$. This can make obtaining eigenvalues by diagonalization computationally challenging. The Shifted Harmonic Approximation (SHA) developed here gives good predictions of properties such as ground state energies, excitation energies and the most probable states in the lowest eigenstates. This is achieved by solving only a system of $k$ equations and diagonalizing $k\times k$ matrices. The SHA gives accurate approximations over wide domains of parameters and in many cases even across phase transitions. The SHA is first illustrated using the Lipkin-Meshkov-Glick (LMG) model and the Canonical Josephson Hamiltonian (CJH) which have $\su{2}$ spectrum generating algebras. Next, we extend the technique to the non-compact $\su{1,1}$ algebra, using the five-dimensional quartic oscillator (5DQO) as an example. Finally, the SHA is applied to a $k$-level Bardeen-Cooper-Shrieffer (BCS) pairing Hamiltonian with fixed particle number. The BCS model has a $\su{2}_1 \oplus \su{2}_2 \oplus \ldots \oplus \su{2}_k$ spectrum generating algebra. An attractive feature of the SHA is that it also provides information to construct basis states which yield very accurate eigenvalues for low-lying states by diagonalizing Hamiltonians in small subspaces of huge Hilbert spaces. For Hamiltonians that involve a smaller number of operators, accurate eigenvalues can be obtained using another technique developed in this thesis: the generalized Rowe-Rosensteel-Kerman-Klein equations-of-motion method (RRKK). The RRKK is illustrated using the LMG and the 5DQO. In RRKK, solving unknowns in a set of $10\times 10$ matrices typically gives estimates of the lowest few eigenvalues to an accuracy of at least eight significant figures. The RRKK involves optimization routines which require initial guesses of the matrix representations of the operators. In many cases, very good initial guesses can be obtained using the SHA. The thesis concludes by exploring possible future developments of the SHA.

Abstract The use of multiple antennas is a fundamental requirement in future wireless networks as it helps to increase the reliability and spectral efficiency of mobile radio links. In this thesis, we study convex optimization based radio resource allocation methods for the downlink of multi-antenna systems. First, the problem of admission control in the downlink of a multicell multiple-input single-output (MISO) system has been considered. The objective is to maximize the number of admitted users subject to a signal-to-interference-plus-noise ratio (SINR) constraint at each admitted user and a transmit power constraint at each base station (BS). We have cast the admission control problem as an ℓ0 minimization problem; it is known to be combinatorial, NP-hard. Centralized and distributed algorithms to solve this problem have been proposed. To develop the centralized algorithm, we have used sequential convex programming (SCP). The distributed algorithm has been derived by using the consensus-based alternating direction method of multipliers in conjunction with SCP. We have shown numerically that the proposed admission control algorithms achieve a near-to-optimal performance. Next, we have extended the admission control problem to provide fairness, where long-term fairness among the users has been guaranteed. We have focused on proportional and max-min fairness, and proposed dynamic control algorithms via Lyapunov optimization. Results show that these proposed algorithms guarantee fairness. Then, the problem of admission control for the downlink of a MISO heterogeneous networks (hetnet) has been considered, and the proposed centralized and distributed algorithms have been adapted to find a solution. Numerically, we have illustrated that the centralized algorithm achieves a near-to-optimal performance, and the distributed algorithm’s performance is closer to the optimal value. Finally, an algorithm to obtain the set of all achievable power-rate tuples for a multiple-input multiple-output hetnet has been provided. The setup consists of a single macrocell and a set of femtocells. The interference power to the macro users from the femto BSs has been kept below a threshold. To find the set of all achievable power-rate tuples, a two-dimensional vector optimization problem is formulated, where we have considered maximizing the sum-rate while minimizing the sum-power, subject to maximum power and interference threshold constraints. This problem is known to be NP-hard. A solution method is provided by using the relationship between the weighted sum-rate maximization and weighted-sum-mean-squared-error minimization problems. The proposed algorithm was used to evaluate the impact of imposing interference threshold constraints and the co-channel deployments in a hetnet. / Tiivistelmä Monen antennin käyttö on perusvaatimus tulevissa langattomissa verkoissa, koska se auttaa lisäämään matkaviestinyhteyksien luotettavuutta ja spektritehokkuutta. Tässä väitöskirjassa tutkitaan konveksiin optimointiin perustuvia radioresurssien allokointimenetelmiä moniantennijärjestelmien alalinkin suunnassa. Ensiksi on käsitelty pääsynvalvonnan ongelmaa alalinkin suuntaan monen solun moni-tulo yksi-lähtö (MISO) -verkoissa. Tavoitteena on maksimoida hyväksyttyjen käyttäjien määrä, kun hyväksytyille käyttäjille on asetettu signaali-häiriö-kohinasuhteen (SINR) rajoitus, ja tukiasemille lähetystehon rajoitus. Pääsynvalvonnan ongelma on muotoiltu ℓ0-minimointiongelmana, jonka tiedetään olevan kombinatorinen, NP-vaikea ongelma. Ongelman ratkaisemiseksi on ehdotettu keskitettyjä ja hajautettuja algoritmeja. Keskitetty optimointialgoritmi perustuu sekventiaaliseen konveksiin optimointiin. Hajautettu algoritmi pohjautuu konsensusoptimointimenetelmään ja sekventiaaliseen konveksiin optimointiin. Ehdotettujen pääsynvalvonta-algoritmien on numeerisesti osoitettu saavuttavan lähes optimaalinen suorituskyky. Lisäksi pääsynvalvontaongelma on laajennettu takaamaan pitkän aikavälin oikeudenmukaisuus käyttäjien välillä. Työssä käytetään erilaisia määritelmiä oikeudenmukaisuuden takaamiseen, ja ehdotetaan dynaamisia algoritmeja pohjautuen Lyapunov-optimointiin. Tulokset osoittavat, että ehdotetuilla algoritmeilla taataan käyttäjien välinen oikeudenmukaisuus. Tämän jälkeen käsitellään heterogeenisen langattoman MISO-verkon pääsynvalvonnan ongelmaa. Edellä ehdotettuja keskitettyjä ja hajautettuja algoritmeja on muokattu tämän ongelman ratkaisemiseksi. Työssä osoitetaan numeerisesti, että sekä keskitetyllä että hajautetulla algoritmilla saavutetaan lähes optimaalinen suorituskyky. Lopuksi on laadittu algoritmi, jolla löydetään kaikki saavutettavissa olevat teho-datanopeusparit heterogeenisessä langattomassa moni-tulo moni-lähtö (MIMO) -verkossa. Verkko koostuu yhdestä makrosolusta ja useasta piensolusta. Piensolutukiasemista makrokäyttäjiin kohdistuvan häiriön teho on pidetty tietyn rajan alapuolella. Kaikkien saavutettavien teho-datanopeusparien löytämiseksi on laadittu kaksiulotteinen vektorioptimointiongelma, jossa maksimoidaan summadatanopeus pyrkien minimoimaan kokonaisteho, kun enimmäisteholle ja häiriökynnykselle on asetettu rajoitukset. Tämän ongelman tiedetään olevan NP-vaikea. Ongelman ratkaisemiseksi käytetään painotetun summadatanopeuden maksimointiongelman, ja painotetun keskineliövirheen minimointiongelman välistä suhdetta. Ehdotettua algoritmia käytettiin arvioimaan häiriörajoitusten ja saman kanavan käyttöönoton vaikutusta heterogeenisessä langattomassa verkossa.

The NP-complete k-SAT problem - decide wether a given formula is satisfiable - is of fundamental importance in theoretical computer science. In this dissertation we study random 4-SAT formulas with > 116 n^2 clauses. These formulas are almost surly unsatisfiable. Here we show the existence of a polynomial time algorithm that certifies the unsatisfiability. Therefore we study the discrepancy of hypergraphs and multigraphs. We also combine spectral techniques with approximation algorithms to achieve the new result. Our new algorithm is adaptable for Not-All-Equal-4-SAT and the 2-colouring of 4-uniform hypergraphs. We also extends the Hajos construction of non k-colourable graphs to non k-colourable uniform hypergraphs. / Das NP-vollständige Problem k-SAT ist von zentraler Bedeutung in der theoretischen Informatik. In der Dissertation werden zufällige 4-SAT-Formeln mit > n^2 vielen Klauseln studiert. Diese Formeln sind mit hoher Wahrscheinlichkeit unerfüllbar. Hier wird erstmalig die Existenz eines Algorithmus gezeigt, der diese Unerfüllbarkeit effizient verifiziert. Hierfür wird die geringe Diskrepanz von Hypergrpahen und Multigraphen betrachtet. Der Schlüssel zu diesem Algorithmus liegt in der Kombination von spektralen Techniken mit Approximationsalgorithmen der klassischen kombinatorischen Optimierung. Der vorgestellte Algorithmus kann auf den effizienten Nachweis der Unerfüllbarkeit von Not-All-Equal-4-SAT-Formeln und die Nicht-2-Färbbarkeit von 4-uniformen Hypergraphen erweitert werden. Es wird ebenfalls eine Erweiterung der Hajos-Konstruktion nicht k-färbbarer Graphen auf nicht k-färbbare uniforme Hypergraphen angegeben.

The NP-complete k-SAT problem - decide wether a given formula is satisfiable - is of fundamental importance in theoretical computer science. In this dissertation we study random 4-SAT formulas with > 116 n^2 clauses. These formulas are almost surly unsatisfiable. Here we show the existence of a polynomial time algorithm that certifies the unsatisfiability. Therefore we study the discrepancy of hypergraphs and multigraphs. We also combine spectral techniques with approximation algorithms to achieve the new result. Our new algorithm is adaptable for Not-All-Equal-4-SAT and the 2-colouring of 4-uniform hypergraphs. We also extends the Hajos construction of non k-colourable graphs to non k-colourable uniform hypergraphs. / Das NP-vollständige Problem k-SAT ist von zentraler Bedeutung in der theoretischen Informatik. In der Dissertation werden zufällige 4-SAT-Formeln mit > n^2 vielen Klauseln studiert. Diese Formeln sind mit hoher Wahrscheinlichkeit unerfüllbar. Hier wird erstmalig die Existenz eines Algorithmus gezeigt, der diese Unerfüllbarkeit effizient verifiziert. Hierfür wird die geringe Diskrepanz von Hypergrpahen und Multigraphen betrachtet. Der Schlüssel zu diesem Algorithmus liegt in der Kombination von spektralen Techniken mit Approximationsalgorithmen der klassischen kombinatorischen Optimierung. Der vorgestellte Algorithmus kann auf den effizienten Nachweis der Unerfüllbarkeit von Not-All-Equal-4-SAT-Formeln und die Nicht-2-Färbbarkeit von 4-uniformen Hypergraphen erweitert werden. Es wird ebenfalls eine Erweiterung der Hajos-Konstruktion nicht k-färbbarer Graphen auf nicht k-färbbare uniforme Hypergraphen angegeben.