Search

The perturbation of the QR decompostion is analyzed from the probalistic point of view. The perturbation error is approximated by a first-order perturbation expansion with high probability where the perturbation is assumed to be random. Different from the previous normwise perturbation bounds using the Frobenius norm, our techniques are used to develop the spectral norm, as well as the entry-wise perturbation bounds for the stochastic perturbation of the QR decomposition. The statistics tends to be tighter (in the sense of the expectation) and more realistic than the classical worst-case perturbation bounds. The novel perturbation bounds are applicable to a wide range of problems in statistics and communications. In this paper, we consider the perturbation bound of the leverage scores under the Gaussian perturbation, the probability guarantees and the error bounds of the low rank matrix recovery, and the upper bound of the errors of the tensor CUR-type decomposition. We also apply our perturbation bounds to improve the robust design of the Tomlinson-Harashima precoding in the Multiple-Input Multiple-Output (MIMO) system. [ABSTRACT FROM AUTHOR]

For logistic regression with massive data, subsampling is an effective way to alleviate the computational challenge. In contrast to most existing methods in the literature that select subsamples randomly, we propose to obtain subsamples in a deterministic way. To be more specific, we measure with leverage scores the influence of each sample to model fitting and select the ones with the highest scores deterministically. We propose a faster alternative method by mimicking the leverage scores with a simple and intuitive form. Our methods pick subsamples catering for constructing a linear classification boundary and hence are more efficient when the subsample size is small. We derive non-asymptotic properties of the two methods regarding the observed information, prediction, and parameter estimation accuracy. Extensive simulation studies and two real applications validate the theoretical results and demonstrate the superiority of our methods. [ABSTRACT FROM AUTHOR]

Two central objects in constructive approximation, the Christoffel-Darbouxkernel and the Christoffel function, are encoding ample information about theassociated moment data and ultimately about the possible generating measures.We develop a multivariate theory of the Christoffel-Darboux kernel in C^d, withemphasis on the perturbation of Christoffel functions and their level sets withrespect to perturbations of small norm or low rank. The statistical notion ofleverage score provides a quantitative criterion for the detection of outliersin large data. Using the refined theory of Bergman orthogonal polynomials, weillustrate the main results, including some numerical simulations, in the caseof finite atomic perturbations of area measure of a 2D region. Methods offunction theory of a complex variable and (pluri)potential theory are widelyused in the derivation of our perturbation formulas.

With rapid advances in information technology, massive datasets are collected in all fields of science, such as biology, chemistry, and social science. Useful or meaningful information is extracted from these data often through statistical learning or model fitting. In massive datasets, both sample size and number of predictors can be large, in which case conventional methods face computational challenges. Recently, an innovative and effective sampling scheme based on leverage scores via singular value decompositions has been proposed to select rows of a design matrix as a surrogate of the full data in linear regression. Analogously, variable screening can be viewed as selecting rows of the design matrix. However, effective variable selection along this line of thinking remains elusive. In this article, we bridge this gap to propose a weighted leverage variable screening method by using both the left and right singular vectors of the design matrix. We show theoretically and empirically that the predictors selected using our method can consistently include true predictors not only for linear models but also for complicated general index models. Extensive simulation studies show that the weighted leverage screening method is highly computationally efficient and effective. We also demonstrate its success in identifying carcinoma related genes using spatial transcriptome data. [ABSTRACT FROM AUTHOR]

End-to-end network delay plays an vital role in distributed services. This delay is used to measure QoS (Quality-of-Service). It would be beneficial to know all node-pair delay information, but unfortunately it is not feasible in practice because the use of active probing will cause a quadratic growth in overhead. Alternatively, using the measured network delay to estimate the unknown network delay is an economical method. In this paper, we adopt the state-of-the-art matrix completion technology to better estimate the network delay from limited measurements. Although the number of measurements required for an exact matrix completion is theoretically bounded, it is practically less helpful. Therefore, we propose an online adaptive sampling algorithm to measure network delay in which statistical leverage scores are used to select potential matrix elements. The basic principle behind is to sample the elements with larger leverage scores to keep the traits of important rows or columns in the matrix. The amount of samples is adaptively decided by a proposed stopping condition. Simulation results based on real delay matrix show that compared with the traditional sampling algorithm, our proposed sampling algorithm can provide better performance (smaller estimation error and less convergence pressure) at a lower cost (fewer samples and shorter processing time). [ABSTRACT FROM AUTHOR]

We consider a refinement of differential privacy --- per instance differential privacy (pDP), which captures the privacy of a specific individual with respect to a fixed data set. We show that this is a strict generalization of the standard DP and inherits all its desirable properties, e.g., composition, invariance to side information and closedness to postprocessing, except that they all hold for every instance separately. We consider a refinement of differential privacy --- per instance differential privacy (pDP), which captures the privacy of a specific individual with respect to a fixed data set. We show that this is a strict generalization of the standard DP and inherits all its desirable properties, e.g., composition, invariance to side information and closedness to postprocessing, except that they all hold for every instance separately. When the data is drawn from a distribution, we show that per-instance DP implies generalization. Moreover, we provide explicit calculations of the per-instance DP for the output perturbation on a class of smooth learning problems. The result reveals an interesting and intuitive fact that an individual has stronger privacy if he/she has small ``leverage score'' with respect to the data set and if he/she can be predicted more accurately using the leave-one-out data set. Simulation shows several orders-of-magnitude more favorable privacy and utility trade-off when we consider the privacy of only the users in the data set. In a case study on differentially private linear regression, provide a novel analysis of the One-Posterior-Sample (OPS) estimator and show that when the data set is well-conditioned it provides $(\epsilon,\delta)$-pDP for any target individuals and matches the exact lower bound up to a $1+\tilde{O}(n^{-1}\epsilon^{-2})$ multiplicative factor. We also demonstrate how we can use a ``pDP to DP conversion'' step to design AdaOPS which uses adaptive regularization to achieve the same results with $(\epsilon,\delta)$-DP.

Matrix completion, i.e., the exact and provable recovery of a low-rank matrix from a small subset of its elements, is currently only known to be possible if the matrix satisfies a restrictive structural constraint-known as incoherence-on its row and column spaces. In these cases, the subset of elements is assumed to be sampled uniformly at random. In this paper, we show that any rank-r n-by-n matrix can be exactly recovered from as few as O(nr log2 n) randomly chosen elements, provided this random choice is made according to a specific biased distribution suitably dependent on the coherence structure of the matrix: the probability of any element being sampled should be at least a constant times the sum of the leverage scores of the corresponding row and column. Moreover, we prove that this specific form of sampling is nearly necessary, in a natural precise sense; this implies that many other perhaps more intuitive sampling schemes fail. We further establish three ways to use the above result for the setting when leverage scores are not known a priori. (a) We describe a provably-correct sampling strategy for the case when only the column space is incoherent and no assumption or knowledge of the row space is required. (b) We propose a two-phase sampling procedure for general matrices that first samples to estimate leverage scores followed by sampling for exact recovery. These two approaches assume control over the sampling procedure. (c) By using our main theorem in a reverse direction, we provide an analysis showing the advantages of the (empirically successful) weighted nuclear/trace-norm minimization approach over the vanilla un-weighted formulation given non-uniformly distributed observed elements. This approach does not require controlled sampling or knowledge of the leverage scores. [ABSTRACT FROM AUTHOR]

This paper deals with the selection of the training dataset in kernel-based methods for function reconstruction, with a focus on kernel ridge regression. A functional analysis is performed which, in the absence of noise, links the optimal sampling distribution to the one minimizing the difference between the kernel matrix and its low-rank Nyström approximation. From this standpoint, a statistical passive sampling approach is derived which uses the leverage scores of the columns of the kernel matrix to design a sampling distribution that minimizes an upper bound of the risk function. The proposed approach constitutes a passive method, able to select the optimal subset of training samples using only information provided by the input set and the kernel, but without needing to know the values of the function to be approximated. Furthermore, the proposed approach is backed up by numerical tests on real datasets. [ABSTRACT FROM AUTHOR]

Cyber and physical attacks threaten the security of distribution power grids. The emerging renewable energy sources such as photovoltaics (PVs) introduce new potential vulnerabilities. Based on the electric waveform data measured by waveform sensors in the distribution power networks, in this paper, we propose a novel high-dimensional data-driven cyber physical attack detection and identification approach (HCADI). Firstly, we analyze the cyber and physical attack impacts (including cyber attacks on the solar inverter causing unusual harmonics) on electric waveforms in distribution power grids. Then, we construct a high dimensional streaming data feature matrix based on signal analysis of multiple sensors in the network. Next, we propose a novel mechanism including leverage score based attack detection and binary matrix factorization based attack diagnosis. By leveraging the data structure and binary coding, our HCADI approach does not need the training stage for both detection and the root cause diagnosis, which is needed for machine learning/deep learning-based methods. To the best of our knowledge, it is the first attempt to use raw electrical waveform data to detect and identify the power electronics cyber/physical attacks in distribution power grids with PVs.