Abstract

Optimization encompasses the mathematical problem of making the best use of the resources available to us, to maximize our reward, or equivalently, minimize our cost. It is a vast field, with important applications, and the importance of optimization has only increased with the rise of machine learning and artificial intelligence - most machine learning problems involve optimization in some way or another. Optimization problems come in various forms. We consider constrained, continous optimization problems with differentiable cost functions and a specific geometric structure on the constraint set. This geometric structure is that of a Riemannian manifold, which are smooth spaces that locally resemble Euclidean space. The paradigm of geometric or Riemannian optimization tackles constrained optimization problems on Euclidean spaces, by translating these problems into unconstrained optimization problems over Riemannian manifolds which may be non-Euclidean spaces. Using concepts from Riemannian geometry, we can develop optimization problems on these manifolds. Since the manifolds have a smaller dimension than the original Euclidean space, these Riemannian optimization algorithms tend to be scalable, fast, and we can prove guarantees on the convergence of these algorithms. This thesis is concerned with the application of geometric optimization techniques to tackle machine learning problems. Specifically, we consider the task of low-rank tensor completion. This problem is an extension of the low-rank matrix completion problem, an important problem with applications in recommendation systems (like the famous Netflix Prize problem). In recent years, there has been an increased interest in multi-dimensional data, which are represented as tensors, higher-dimensional analogues of matrices. Capturing this data as a matrix fundamentally alters the structure, and causes loss of information. This motivates us to study tensor problems. Tensor completion is one such problem, where we attempt to recover the original tensor given sparse observations, under the assumption that the tensor has a small rank. It has applications in visual data inpainting and recommender systems, among others. As an extension, we study the general structured tensor completion problem, where, in addition to the low rank structure, the tensor must also satisfy some structural constraints such as nonnegativity. The dual problem for the structured tensor completion problem has a constraint set that is a Riemannian manifold. We develop optimization algorithms for this problem, provide experimental results to show the method is competitive, and provide theoretical guarantees for the recovered tensor.

Abstract

It is observed that internal repeats in eukaryotic proteins are three times more likely compared to in prokaryotes suggesting possible advantages provided to the organism. Functions specific to eukaryotes such as connective tissue proteins, cytoskeletal proteins, ribonucleoproteins, muscle proteins, brain and synaptic proteins, and cell adhesion proteins are observed to have internal repeats. The other major advantage of studying protein repeats is in their ability to confer multiple binding and structural roles on proteins. With a high frequency of occurrence in humans, 30%, tandem repeat proteins have been linked to various complex diseases, e.g., the role of Leucine-rich repeats in Parkinson's disease, ANK, HEAT, and ARM repeats in cancer, etc. A large surfaceto-volume ratio, good target affinity, smaller size, and stability in the shape of repeat proteins make them important for biomedical applications. For example, designed ankyrin repeat proteins (DARPins) are being developed for targeted therapies. Due to fewer constraints at the sequence level, detection of repeats at the structure level is desirable. Here we propose a deep learning-based approach for the detection of two major classes of structural repeats, namely, Class III and Class IV repeats in Kajava’s classification, which covers over 90% of known structural repeats and their repeat region. We approached the problem by exploiting the presence of structural information in the protein distance matrix which captures the internal distances between residues in a protein chain. Performance evaluation is carried out by comparison with other state-of-the-art methods and annotations in UniProt. Lastly, we have discussed the improvement done in the development of the NAPS Portal (Network Analysis of Protein Structures) which is used by researchers to visualize and to perform analyses of different protein structures.

Abstract

The process of data mining discovers interesting knowledge from large amounts of data. Given a large amount of data, we have several data mining software systems for summarizing/characterizing, extracting frequent patterns and association rules, classification, and clustering tasks. The data mining based systems are employed to improve the performance of e-commerce systems, marketing, search systems, banking, healthcare, etc. Investigating data mining approaches to extract new knowledge from the given data is one of the active research areas. Graph model is widely employed to model the real world. For example, a chemical compound, a protein-ligand complex, and an XML document can be modeled as a graph or a graph transaction. In the literature, the topic of extracting the knowledge of frequent subgraphs from the given Graph Transactional Dataset (GTD) has been extensively studied. It has been shown that such knowledge could help in the drug discovery process. So far, in the literature, the issue of extracting coverage-related knowledge from GTD has not yet been explored. In this thesis, we propose new data mining models and approaches to extract two types of knowledge patterns from GTDs. Motivated by the issues in the process of drug discovery, as the first contribution, we propose the model and approach to extract the coverage-related knowledge of potential subgraph patterns from the given GTD. A subgraph pattern is a set of subgraphs. We consider that a subgraph covers the graph transaction if it belongs to that graph transaction. A subgraph pattern is considered as Subgraph Coverage Pattern (SCP) if the ratio of the union of the graph transactions covered by the subgraphs of the subgraph pattern to the size of GTD is not less than a user-given threshold value. We have defined three metrics to characterize an SCP. First, the relative frequency metric ensures that each subgraph of an SCP should appear in the threshold number of graph transactions. Second, the coverage support metric ensures that the union of graph transactions covered by each subgraph of SCP should satisfy the threshold percentage of GTD. Third, the overlap ratio metric ensures that the overlap ratio among the graph transactions covered by individual subgraphs of SCP satisfies overlap ratio constraint. Given a GTD and the user-given threshold values of relative frequency, coverage support and overlap ratio, the problem is to extract all SCPs from the given GTD. A straightforward approach requires the extraction of all possible subgraphs from GTD and generation of all possible subgraph patterns. In addition, for each subgraph pattern, it requires expensive graph-based computation of relative frequency, coverage support and overlap ratio to identify all SCPs of GTD. In this model, we propose the notions of the potential subgraphs, flat transactional modeling, and employ an overlap ratio-based candidate pruning heuristic for efficiently extracting SCPs from GTD. As the second contribution, with the motivation to improve the process of drug cocktail discovery, we have proposed the model and approach to extract the coverage-related knowledge of graph transactional patterns from the given GTD. A graph transactional pattern is a set of graph transactions. A drug compound can be modeled as a graph transaction, and its fragments can be modeled as subgraphs. A set of all fragments extracted from GTD is considered as a fragment set. We consider that a graph transaction covers a fragment if the fragment belongs to that graph transaction. A graph transactional pattern is considered as a Graph Transactional Coverage Pattern (GTCP) if the ratio of the union of fragments covered by each of its graph transactions to the size of the fragment set satisfies the coverage constraint. We have defined three metrics to characterize GTCP. First, the graph transactional coverage metric ensures that each graph of GTCP should cover at least threshold percentage of fragments in the fragment set. Second, the graph transactional pattern coverage metric ensures that the union of fragments covered by each graph transaction of GTCP should satisfy the coverage constraint. Third, the overlap ratio metric ensures that the overlap ratio among the fragments covered by individual graph transactions of GTCP should satisfy the overlap ratio constraint. Given a GTD and the threshold values of graph transactional coverage, graph transactional pattern coverage, and overlap ratio, the problem is to extract all GTCPs from given GTD. A straightforward approach involves extracting all of the possible fragments from GTD and generation of all possible graph transactional patterns, which increase exponentially as the size of GTD increases. In addition, for each candidate graph transactional pattern, requires expensive graph-based computation of graph transactional pattern coverage and overlap ratio for extracting all GTCPs from GTD. In this work

Abstract

The footprint of partial or fully autonomous vehicles is increasing gradually with time. The existenceand availability of the necessary modern infrastructure are crucial for the widespread use of autonomousnavigation. One of the most critical efforts in this direction is to build and maintain HD maps efficientlyand accurately. The information in HD maps is organized in various levels 1) Geometric layer, 2)Semantic layer and 3) Map prior’s layer. The conventional approaches to capturing and extractinginformation at different HD map levels rely heavily on huge sensor networks and manual annotation.This is not scalable to create HD maps for massive road networks. We propose two novel solutionsto address the mentioned problems in this work. The first solution deals with the generation of thegeometric layer with parametric information of the road scene and other one to update information onroad infrastructure and traffic violations in the semantic layer.Firstly, the creation of the geometric layer of the HD map requires understanding the road layout interms of structure, number of lanes, lane width, curvature, etc. Prediction of these attributes as part ofa generalizable parametric model with which road layout can be rendered would suite the creation of ageometric layer. Many previous works that tried to solve this problem rely only on ground imagery andare limited by the narrow field of view of the camera, occlusions, and perspective shortening. This workdemonstrates the effectiveness of using aerial imagery as an additional modality to overcome the abovechallenges. We propose a novel architecture, Unified, that combines aerial and ground imagery featuresto infer scene attributes. We quantitatively evaluate on the KITTI dataset and show that our Unifiedmodel outperforms prior works. Since this dataset is limited to road scenes close to the vehicle, we sup-plement the publicly available Argoverse dataset with scene attribute annotations and evaluate far-awayscenes. We quantitatively and qualitatively show the importance of aerial imagery in understanding roadscenes, especially in regions farther away from the ego-vehicle.Finally, we also propose a simple mobile imaging setup to address and audit several common prob-lems in urban mobility and road safety, which can enrich the information in a semantic layer of HDmaps. Recent computer vision techniques are used to identify street irregularities (including missinglane markings and potholes), absence of street lights, and defective traffic signs using videos obtainedfrom a moving camera-mounted vehicle. Beyond the inspection of static road infrastructure, we alsodemonstrate the applicability of mobile imaging solutions to spot traffic violations. We validate ourproposal on the long stretches of unconstrained road scenes covering over 2000Km and discuss practi-cal challenges in applying computer vision techniques at such a scale. Exhaustive evaluation is carried

Abstract

In recent years there has been a lot of research work regarding media synthesis and generation using artificial intelligence. Artificial intelligence programs like Dall-e can generate an image from a phrase. StyleGAN from Nvidia can create images of the faces and bodies of people who do not exist. Video manipulation using deep learning can change one person’s likeness to another using deep learning and neural networks. Programs like GPT-3 can generate text of such quality that it is hard to determine whether a human wrote it on not. There has also been much progress in generating music using artificial intelligence. MuseNet by Openai, a deep neural network that can produce 4-minute musical pieces that have different instruments and styles. Jukebox by Openai, a neural network that produces music and simple singing as raw audio for a few genres and artistic styles. WaveNet from Deepmind, a generative model that generates audio waveforms, can generate background/Ambient music using deep learning. There exists a lot of research work that takes as its subject western popular music and classical music to generate new performances using old performances by an artist, but there exists no research work for the generation of improvised sequences for North Indian classical music. This thesis presents three methods to generate improvised sequence generation in North Indian classical music. The first method we propose uses context-free grammar, which can be used to generate these sequences. We also discuss how to generate these sequences and problems with this method. We illustrate this method by preparing context-free grammar for yaman raga ¯ . In our second method to this problem, We propose a bi-gram language model to generate improvised sequences. We propose a bi-gram model to evaluate this approach. To assess this model, we introduce our Pt. Ajoy Chakraborty Bhoopali Compositions Data Set. All compositions in this data set are by a single artist, Pandit Ajoy Chakraborty. We evaluate the bi-gram model on this data-set to achieve a TOP1 accuracy of 46.63 percent and a TOP-3 accuracy of 83.50 percent on this data set. We discuss how to qualify and generate new improvised sequences using this model. We also discuss the disadvantages of this model. In our third method to the problem, we propose a LSTM-RNN based model to generate improvised sequences. We discuss the motivation for this method. We also discuss model architecture and training settings. We evaluate our first LSTM-RNN based model on Pt. Ajoy Chakraborty Bhoopali Compositions Dataset. We achieve TOP-1 accuracy of 45.56 percent and TOP-3 accuracy of 80.42 percent. We discuss how to qualify and generate a new improvised sequence using this model. Further, we also discuss the disadvantages of this method.

Abstract

Centrality measures are used to quantify various notions of importance of nodes in a network. These measures find application in social network analysis, the study of disease spread, and the like. Since the networks of interest are usually large, parallelism has become a powerful tool to compute these measures. We study parallel algorithms for the percolation centrality measure which extends the betweennesscentrality measure by incorporating a time dependent state variable with every node. We present parallel algorithms that compute the source-based and source-destination variants of the percolation centrality values of nodes in a network. Our algorithms extend the algorithm of Brandes, introduce optimizations aimed at exploiting the structural properties of graphs, and extend the algorithmic techniques introduced by Sariyuce et al. [38] in the context of centrality computation. However, for some of these applications, it is important to study how these centrality values change when there are changes to the underlying network. As a result, parallel algorithms that study how to update these values due to changes to the graph are gaining research interest. We present parallel algorithms to handle both changes to the percolation value of a batch of vertices and the addition and deletion of a batch of edges to the graph. We implement and benchmark our dynamic algorithms on an Nvidia Tesla V100 GPU. Our experiments on a collection of real-world graphs indicate that our algorithms achieve speedups of 1.59× for edge updates, and 63.02× for vertex percolation updates over state-of-the-art static algorithms for a batch of 100 edges and vertices respectively.

Abstract

The study of quantum entanglement is significant for the development of Quantum Information science. Hence its detection becomes very vital. Detection of quantum entanglement is an NP-hard problem, and this is why we don’t have a generalized solution for the detection of quantum entanglement. There are many ways to detect quantum entanglement, but our study will mainly focus on detecting entanglement using the mathematical theory of positive but not completely positive maps. Positive but not completely positive maps applied to a subsystem of a bipartite quantum state are a central tool in characterizing entanglement in a bipartite system. In this study, we utilize a particular type of non-Markovianity known as the eternal non-Markovianity to construct a non-complete positive map. In the multipartite case, the direct application of a positive but not completely positive map does not work. It fails to capture the distinction among different classes of multipartite entanglement. We thus generalise this bipartite concept to the multipartite setting by introducing a special non-positive maps that are positive on the subset of bi-separable states, but can map to a non-positive element if applied to a genuine multipartite entangled state. We further propose a witness operator to detect genuinely multipartite entangled states experimentally based on this theory. Our study sheds light on a hitherto unexplored connection between entanglement theory and quantum non-Markovianity.

Abstract

The 3D reconstruction of a human from a monocular RGB image is an interesting yet very challenging research problem in the field of computer vision. It has various applications in the movie industry, the gaming industry, and AR/VR applications. Hence it is important to recover detailed geometric 3D reconstruction of humans in order to enhance the realism. The problem is ill-posed in nature owing to high freedom of human pose, self-occlusions, loose clothing, camera viewpoint, and illumination. Though it is possible to generate accurate geometric reconstructions using structured light scanners or multi-view cameras these are cost expensive and require a specific setup e.g., numerous cameras, controlled illumination, etc. With the current advancement of deep learning techniques, the focus of the community shifted to the 3D reconstruction of people from monocular RGB images. The goal of the thesis is toward 3D Human Digitization of people in loose clothing with accurate person-specific details. The problem of reconstruction of people in loose clothing is difficult as the topology of clothing is different from the human body. A multi-layered shape representation called PeeledHuman was able to deal with loose clothing and occlusions but it suffered from discontinuity or distorted body parts in the occluded regions. To overcome this we propose peeled semantic segmentation maps which provide the semantic information of the body parts across multiple peeled layers. These Peeled semantic maps help the network in predicting consistent depth for the pixels belonging to the same body part across different peeled maps. Our proposed Peeled Segmentation maps help in improving reconstruction both quantitatively and qualitatively. Additionally, the 3D semantic segmentation labels have various applications, for example, can be used to extract the clothing from the reconstructed output. The face plays an important role in 3D Human digitization, it gives a person their identity and the realism enhances with high-frequency facial details. However, the face appears in a smaller region of the image which captures the complete body and makes the task of high-fidelity face reconstruction along with the body even more challenging. We reconstruct person-specific facial geometry along with the complete body by incorporating a facial prior and refining it further using our proposed framework. Another common challenge faced by the existing methods is the surface noise i.e, false geometric edges generated because of the textural edges present in the image space. We address this problem by incorporating a wrinkle map prior that distinguishes the geometrical from the textural edges coming from image space. In summary, in this thesis, we address the problem of 3D human digitization from monocular images. We evaluate our proposed solution on various existing 3D human datasets and demonstrate that our proposed solutions outperform the existing state-of-the-art methods. The limitations present in the proposed methods were mentioned and potential solutions on how to address them have been briefly discussed. In the end, some future directions that can be potentially explored based on the proposed solutions have been discussed. Finally, we proposed efficient and robust methods to recover accurate and personalized 3D humans from images.

Abstract

Semiconductor Industry has undergone rapid miniaturization in recent decades due to advances in manufacturing technology and the demand for more functionality per chip area. However, scaling down metal-oxide-semiconductor field-effect transistors (MOSFETs) offer many advantages in terms of functionality and speed; it also poses many challenges like increased leakage power. A shrink in device size leads to lowering the threshold voltage to meet the functionality metrics. Due to the inverse relationship of leakage power with the threshold voltage, a rapid increase in leakage power is encountered. In deep sub-micron technologies, static power is dominant over dynamic power, leading to an urgent need for leakage reduction techniques. The primary outcome of scaling down transistors is a reduction in propagation delay. This is achieved by the lowering of threshold voltage and oxide thickness. However, as this comes with the higher cost of increased sub-threshold leakage current, scaling down of Vt is restricted. Hence, the need for delay optimization techniques. Another major issue associated with the miniaturization of MOSFETs is the variation of process parameters. Due to scaled-down devices, slight variation in process parameters impacts significantly on performance and yield of the devices. In addition, external environmental changes like temperature and supply voltage variations also affect the performance parameters like delay and leakage by affecting device densities and switching activities of various blocks. Hence, Process variations, Voltage and Temperature (PVT) are the key factors to be considered while optimizing a circuit. Furthermore, aging due to Negative-bias temperature instability (NBTI) affects the delay of the circuit. So, NBTI aging should be considered in delay optimization, for manufacturing more reliable and long-life devices. The above factors call for the indispensable need for leakage-delay optimization techniques. Hence, in this research, we propose a multi-objective algorithm-based leakage-delay optimization approach. We used various intuitive multi-objective algorithms to model device parameters such as the Width (W) and Length (L) of a MOSFET. Considering PVT variations for low-power optimization and Process, Supply Voltage, Temperature and Aging (PVTA) variations for high-performance applications, we have applied various swarm-based and genetic algorithms on basic and complex benchmark circuits and obtained up to 70% optimization of Leakage power with PVT and 30% optimization of propagation delays with PVTA conditions. Further, we developed an automated framework of algorithms to analyze the characteristics of a given circuit, choose the appropriate algorithm and load-based sizing to replace in a given circuit for obtaining the required performance metrics. In addition, we have proposed Backward traversal replacement and Partitioning large cells methods for enhanced optimisation of complex cells. The next step to further optimize this optimization process of the circuits is to eliminate the inherent extensive run time taken by the SPICE tool. The algorithm optimization process involves the calculation of circuit performances like leakage and propagation delay for huge samples. moreover, with the scaled down technology nodes, statistical variation aware analysis has gained importance, which also involves large number of circuit performance calculations. SPICE tool is widely used to calculate the circuit performances and computing results of an extensive sample set with the SPICE tool is time complex. Hence, we proposed a statistical variation aware estimation models based on machine learning techniques like Polynomial Regression and Artificial Neural Networks (ANN), which replaces the SPICE tool with <1% Error and 10,000 times reduction in time complexity.

Abstract

There is no doubt that videos are today’s most popular content consumption method. With the rise of the streaming giants such as YouTube, Netflix, etc., video content is accessible to more people. Naturally, video content creation has also increased to cater to the rising demand. In order to reach out to a wider audience, the creators dub their content. An important aspect of dubbing is not only changing the speech but also lip synchronizing the speaker in the video. Talking-face video generation works have achieved state-of-the-art results in synthesizing videos with accurate lip synchronization. However, most of the previous works deal with low-resolution talking-face videos (up to 256 × 256 pixels), thus, generating extremely high-resolution videos still remains a challenge. Also, with advancements in internet and camera tech more and more number of people are able to create video content and that too in ultra high resolution such as 4K (3840 × 2160). In this thesis, we take a giant leap and propose a novel method to synthesize talking-face videos at resolutions as high as 4K! Our task presents several key challenges: (i) Scaling the existing methods to such high resolutions is resource-constrained, both in terms of compute and the availability of very high-resolution datasets, (ii) The synthesized videos need to be spatially and temporally coherent. The sheer number of pixels that the model needs to generate while maintaining the temporal consistency at the video level makes this task non-trivial and has never been attempted in literature. We propose to train the lip-sync generator in a compact Vector Quantized (VQ) space for the first time to address these issues. Our core idea to encode the faces in a compact 16 × 16 representation allows us to model high-resolution videos. In our framework, we learn the lip movements in the quantized space on the newly collected 4K Talking Faces (4KTF) dataset. Our approach is speaker agnostic and can handle various languages and voices. We benchmark our technique against several competitive works and show that we can achieve a remarkable 64-times more pixels than the current state-of-the-art! Now, how to edit videos using the above algorithm or any other deep learning algorithm? To do so, the person has to download the source code of the required method and run the code manually. How amazing would it be if people could use the deep learning techniques in video editors with a click of a single button? In this thesis, we also propose a video editor based on OpenShot with several state-of-theart facial video editing algorithms as added functionalities. Our editor provides an easy-to-use interface to apply modern lip-syncing algorithms interactively. Apart from lip-syncing, the editor also uses audio and facial re-enactment to generate expressive talking faces. The manual control improves the overall experience of video editing without missing out on the benefits of modern synthetic video generation algorithms. This control enables us to lip-sync complex dubbed movie scenes, interviews, television shows, and other visual content. Furthermore, our editor provides features that automatically translate lectures from spoken content, lip-sync of the professor, and background content like slides. While doing so, we also tackle the critical aspect of synchronizing background content with the translated speech. We qualitatively evaluate the usefulness of the proposed editor by conducting human evaluations. Our evaluations show a clear improvement in the efficiency of using human editors and an improved video generation quality