Discrimination problems are of significant interest in the machine learning literature. There has been growing interest in extending traditional vector-based machine learning techniques to their matrix forms. In this article, we investigate the statistical properties of the nuclear-norm-based regularized linear support vector machines (SVMs), in particular establishing the convergence rate of the estimator in the high-dimensional setting. Furthermore, within the distributed estimation paradigm, we propose a communication-efficient estimator that can achieve the same convergence rate. We illustrate the performances of the estimators via some simulation examples and an empirical data analysis.

This work is concerned with the estimation problem of linear model when the sample size is extremely large and the data dimension can vary with the sample size. In this setting, the least square estimator based on the full data is not feasible with limited computational resources. Many existing methods for this problem are based on the sketching technique which uses the sketched data to perform least square estimation. We derive fine-grained lower bounds of the conditional mean squared error for sketching methods. For sampling methods, our lower bound provides an attainable optimal convergence rate. Our result implies that when the dimension is large, there is hardly a sampling method can have a faster convergence rate than the uniform sampling method. To achieve a better statistical performance, we propose a new sketching method based on data averaging. The proposed method reduces the original data to a few averaged observations. These averaged observations still satisfy the linear model and are used to estimate the regression coefficients. The asymptotic behavior of the proposed estimation procedure is studied. Our theoretical results show that the proposed method can achieve a faster convergence rate than the optimal convergence rate for sampling methods. Theoretical and numerical results show that the proposed estimator has good statistical performance as well as low computational cost.

Kernel Fisher discriminant (KFD) is a popular tool as a nonlinear extension of Fisher's linear discriminant, based on the use of the kernel trick. However, its asymptotic properties are still rarely studied. We first present an operator-theoretical formulation of KFD which elucidates the population target of the estimation problem. Convergence of the KFD solution to its population target is then established. However, the complexity of finding the solution poses significant challenges when n is large and we further propose a sketched estimation approach based on a m×n sketching matrix which possesses the same asymptotic properties (in terms of convergence rate) even when m is much smaller than n. Some numerical results are presented to illustrate the performances of the sketched estimator.

Fast Johnson-Lindenstrauss Transform (FJLT) and Sparse Johnson-Lindenstrauss Transform (SJLT) are two important oblivious subspace embeddings. So far, the developments of these two methods are almost orthogonal. In this work, we propose an iterative algorithm for oblivious subspace embedding which makes a connection between these two methods. The proposed method is built upon an iterative implementation of FJLT and is equipped with several theoretically motivated modifications. One important strategy we adopt is the early stopping strategy. On the one hand, the early stopping strategy makes our algorithm fast. On the other hand, it results in a sparse embedding matrix. As a result, the proposed algorithm is not only faster than the FJLT, but also faster than the SJLT with the same degree of sparsity. We present a general theoretical framework to analyze the embedding property of sparse embedding methods, which is used to prove the embedding property of the proposed method. This framework is also of independent interest. Lastly, we conduct numerical experiments to verify the good performance of the proposed algorithm.

This work is concerned with the overdetermined linear least-squares problem for large scale data. We generalize the iterative Hessian sketching (IHS) algorithm and propose a new sketching framework named iterative double sketching (IDS) which uses approximations for both the gradient and the Hessian in each iteration. To understand the behavior of the IDS algorithm and choose the optimal hyperparameters, we derive the exact limit of the conditional prediction error of the IDS algorithm in the setting of Gaussian sketching. Guided by this theoretical result, we propose an efficient IDS algorithm via a new class of sequentially related sketching matrices. We give a non-asymptotic analysis of this efficient IDS algorithm which shows that the proposed algorithm achieves the state-of-the-art trade-off between accuracy and efficiency.

Chatting with nearby interested strangers instantly in location-based mobile social network (LMSN) has become increasingly popular. Currently, friend recommendation relies only on the simple and limited user profiles, and is agnostic to users' offline behaviors in the real world. For the first time, we focus on utilizing the user's check-in behaviors in the real world, instead of the general acquaintance-based social circles, to instantly recommend nearby strangers to make friends. However, bridging nearby strangers with similar check-in behaviors instantly has some new characteristics, such as lack of common friends and interaction histories, temporal, spatial and user three-dimensional correlation, and sparseness of check-ins. Most existing work about friend recommendations mainly focuses on making friends within the acquaintance-based social circles, and has not fully considered these new characteristics mentioned above. Therefore, how to catch the ephemeral opportunity to recommend nearby interested strangers instantly remains a challenge. In this paper, we present to use “Encounter” probability to measure the behavior similarity of two strangers in the real world based on their check-in histories. To address the sparseness challenge of check-in data, a Kernel Density Estimation (KDE)-based user check-in probability estimation method considering the spatiotemporal dimensions is proposed to estimate each user's check-in probability distribution with time at each spot. Finally, we use a large-scale user check-in dataset of Gowalla to validate the effectiveness of this approach. The experimental results show that our approach outperforms other commonly used similarity computation methods.

Remote sensing inversion problem is always ill-posed. However, regularization aims at turning the ill-posed problems into certainty. In this paper, taking the linear kernel-driven model as an example, we put forward the maximum entropy algorithm based on information theory to determine the Tikhonov regularization parameter. Then, analyse and compare it with other mature methods. Result shows that the maximum entropy algorithm has advantages when the variance of the observations' noise is small or uncertainty of the prior knowledge is not too large.

We take the kernel-driven model as an example, focus on the information content definition and calculation of multi-angular remote sensing (MARS) data. We study four methods to measure the information content of MARS data: Fisher statistic, information entropy, determinant and sum of the diagonal elements of the information matrix, how to use the Fisher statistic theory and information entropy to measure the information content of MARS data, to calculate the information content of the dataset on the three unknowns for different subsets of the data. The analyses show that information entropy is a good tool for measuring information content of MARS data.