The goal of the thesis is to extend the kernel methods to matrix factorization(MF) for collaborative ltering(CF). In current literature, MF methods usually assume that the correlated data is distributed on a linear hyperplane, which is not always the case. The best known member of kernel methods is support vector machine (SVM) on linearly non-separable data. In this thesis, we apply kernel methods on MF, embedding the data into a possibly higher dimensional space and conduct factorization in that space. To improve kernelized matrix factorization, we apply multi-kernel learning methods to select optimal kernel functions from the candidates and introduce L2-norm regularization on the weight learning process. In our empirical study, we conduct experiments on three real-world datasets. The results suggest that the proposed method can improve the accuracy of the prediction surpassing state-of-art CF methods.

This dissertation has two parts. In the first part, we focus on random inner product kernel matrices. Under various assumptions, many authors have proved that the limiting empirical spectral distribution (ESD) of such matrices A converges to the Marchenko- Pastur distribution. Here, we establish the corresponding rate of convergence. The strategy is as follows. First, we show that for z = u + iv ∈ C, v > 0, the distance between the Stieltjes transform m_A (z) of ESD of matrix A and Machenko-Pastur distribution m(z) is of order O (log n \ nv). Next, we prove the Kolmogorov distance between ESD of matrix A and Marchenko-Pastur distribution is of order O(3\log n\n). It is the less sharp rate for much more general class of matrices. This uses a Berry-Esseen type bound that has been employed for similar purposes for other families of random matrices. In the second part, random geometric graphs on the unit sphere are considered. Observing that adjacency matrices of these graphs can be thought of as random inner product matrices, we are able to use an idea of Cheng-Singer to establish the limiting for the ESD of these adjacency matrices. / Mathematics

Polar codes, introduced by Arikan in 2009, have attracted considerable interest as an asymptotically capacity-achieving code with sufficient performance advantages to merit inclusion in the 5G standard. Polar codes are constructed directly from an explicit model of the communication channel, so their performance is dependent on a detailed understanding of the transmission environment. We partially remove a basic assumption in coding theory that channels are identical and independent by extending polar codes to several types of channels with memory, including periodic Markov processes and Information Regular processes. In addition, we consider modifications to the polar code construction so that the inclusion of a shared secret in the frozen set naturally produces encryption via one-time pad. We describe one such modification in terms of the achievable frozen sets which are compatible with the polar code automorphism group. We then provide a partial characterization of these frozen sets using an explicit construction for the Linear Extension Diameter of channel entropies. / Doctor of Philosophy / Efficient, reliable communication has become an essential component of modern society. Error-correcting codes allow for the use of redundant symbols to fix errors in transmission. While it has long been known that communication channels have an inherent capacity describing the optimal redundancy required for reliable transmission, explicit constructions which achieve this capacity have proved elusive. Our focus is the recently discovered family of polar codes, which are known to be asymptotically capacity-achieving. Polar codes also perform well enough in practice to merit inclusion in the 5G wireless standard shortly after their creation. The polarization process uses an explicit model of the channel and a recursive construction to concentrate errors in a few symbols (called the frozen set), which are then simply ignored. This reliance on an explicit channel model is problematic due to a long-standing assumption in coding theory that the probability of error in each symbol is identical and independent. We extend existing results to explore persistent sources of interference modelling environments such as nearby power lines or prolonged outages. While polar codes behave quite well in these new settings, some forms of memory can only be overcome using very long codewords. We next explore an application relating to secure communication, where messages must be recovered by a legitimate receiver but not by an eavesdropper. Polar codes behave quite well in this environment as well, as we can separately compute which symbols can be recovered by each party and use only those with the desired properties. We extend a recent result which proposes the use of a shared secret in the code construction to further complicate recovery by an eavesdropper. We consider several modifications to the construction of polar codes which allow the shared secret to be used for encryption in addition to the existing information theoretic use. We discover that this task is closely related to the unsolved problem of determining which symbols are in the frozen set for a particular channel. We conclude with partial results to this problem, including two choices of frozen set which are, in some sense, maximally separated.

The central theme of the thesis is to study linear and non linear SVM formulations in the presence of uncertain observations. The main contribution of this thesis is to derive robust classfiers from partial knowledge of the underlying uncertainty. In the case of linear classification, a new bounding scheme based on Bernstein inequality has been proposed, which models interval-valued uncertainty in a less conservative fashion and hence is expected to generalize better than the existing methods. Next, potential of partial information such as bounds on second order moments along with support information has been explored. Bounds on second order moments make the resulting classifiers robust to moment estimation errors. Uncertainty in the dataset will lead to uncertainty in the kernel matrices. A novel distribution free large deviation inequality has been proposed which handles uncertainty in kernels through co-positive programming in a chance constraint setting. Although such formulations are NP hard, under several cases of interest the problem reduces to a convex program. However, the independence assumption mentioned above, is restrictive and may not always define a valid uncertain kernel. To alleviate this problem an affine set based alternative is proposed and using a robust optimization framework the resultant problem is posed as a minimax problem. In both the cases of Chance Constraint Program or Robust Optimization (for non-linear SVM), mirror descent algorithm (MDA) like procedures have been applied.