Search

AbstractLow-rank approximation is a popular strategy to tackle the “big n problem” associated with large-scale Gaussian process regressions. Basis functions for developing low-rank structures are crucial and should be carefully specified. Predictive processes simplify the problem by inducing basis functions with a covariance function and a set of knots. The existing literature suggests certain practical implementations of knot selection and covariance estimation; however, theoretical foundations explaining the influence of these two factors on predictive processes are lacking. In this paper, the asymptotic prediction performance of the predictive process and Gaussian process predictions are derived and the impacts of the selected knots and estimated covariance are studied. The use of support points as knots, which best represent data locations, is advocated. Extensive simulation studies demonstrate the superiority of support points and verify our theoretical results. Real data of precipitation and ozone are used as examples, and the efficiency of our method over other widely used low-rank approximation methods is verified. [ABSTRACT FROM AUTHOR]

The spectrum of a kernel matrix significantly depends on the parameter values of the kernel function used to define the kernel matrix. This makes it challenging to design a preconditioner for a regularized kernel matrix that is robust across different parameter values. This paper proposes the adaptive factorized Nyström (AFN) preconditioner. The preconditioner is designed for the case where the rank k of the Nyström approximation is large, i.e., for kernel function parameters that lead to kernel matrices with eigenvalues that decay slowly. AFN deliberately chooses a well-conditioned submatrix to solve with and corrects a Nyström approximation with a factorized sparse approximate matrix inverse. This makes AFN efficient for kernel matrices with large numerical ranks. AFN also adaptively chooses the size of this submatrix to balance accuracy and cost. [ABSTRACT FROM AUTHOR]

This paper presents a QR decomposition based low-rank approximation algorithm for training and prediction in Gaussian process regression. Conventional low-rank methods like FITC, Nyström, etc., rely on low-rank approximations to the full kernel matrix that are derived from a set of representative data points. Training with FITC involves the selection of these representative points and is computationally intensive when the dimension of the dataset is large. Prediction accuracy of Nyström suffers when the number of representative points is small or when the length scale is small. The algorithm proposed here uses the thin QR decomposition of the low-rank matrix used in the Nyström approximation. We show that the marginal likelihood and its derivatives needed for training can be split into the subspace belonging to that approximation and its orthogonal complement. During prediction, we further restrict the target vectors into this subspace and thus eliminate the numerical error caused by very low noise variance. Use of the QR factorization improves the training and prediction performance. Experiments on real and synthetic data show that our approach is more accurate and faster than conventional methods. Our algorithm performs well at low length scales and achieves the prediction accuracy comparable to the full kernel matrix approach even for low rank approximations, without the need to optimize the representative points. This results in a simpler and faster approximation that could be used to scale Gaussian process regression to large datasets. [ABSTRACT FROM AUTHOR]

This study provides a computable, direct, and mathematically rigorous approximation to the differential geometry of class manifolds for high-dimensional data, along with non-linear projections from input space onto these class manifolds. The tools are applied to the setting of neural network image classifiers, where we generate novel, on-manifold data samples and implement a projected gradient descent algorithm for on-manifold adversarial training. The susceptibility of neural networks (NNs) to adversarial attack highlights the brittle nature of NN decision boundaries in input space. Introducing adversarial examples during training has been shown to reduce the susceptibility of NNs to adversarial attack; however, it has also been shown to reduce the accuracy of the classifier if the examples are not valid examples for that class. Realistic “on-manifold” examples have been previously generated from class manifolds in the latent space of an autoencoder. Our study explores these phenomena in a geometric and computational setting that is much closer to the raw, high-dimensional input space than what can be provided by VAE or other black box dimensionality reductions. We employ conformally invariant diffusion maps (CIDM) to approximate class manifolds in diffusion coordinates and develop the Nyström projection to project novel points onto class manifolds in this setting. On top of the manifold approximation, we leverage the spectral exterior calculus (SEC) to determine geometric quantities such as tangent vectors of the manifold. We use these tools to obtain adversarial examples that reside on a class manifold, yet fool a classifier. These misclassifications then become explainable in terms of human-understandable manipulations within the data, by expressing the on-manifold adversary in the semantic basis on the manifold.

This paper introduces the Nyström preconditioned conjugate gradient (PCG) algorithm for solving a symmetric positive-definite linear system. The algorithm applies the randomized Nyström method to form a low-rank approximation of the matrix, which leads to an efficient preconditioner that can be deployed with the conjugate gradient algorithm. Theoretical analysis shows that the preconditioned system has constant condition number as soon as the rank of the approximation is comparable with the number of effective degrees of freedom in the matrix. The paper also develops adaptive methods that provably achieve similar performance without knowledge of the effective dimension. Numerical tests show that Nyström PCG can rapidly solve large linear systems that arise in data analysis problems, and it surpasses several competing methods from the literature. [ABSTRACT FROM AUTHOR]

We present an effective method for supervised landmark selection in sparse Nyström approximations of kernel matrices for structured data. Our approach transforms structured non-vectorial input data, like graphs or text, into a dissimilarity representation, facilitating the identification of data-distribution-informed landmarks through prototype-based learning. Experimental results indicate competitive approximation quality when compared to existing strategies, showcasing the advantageous impact of incorporating more information into the Nyström landmark selection process. This positions our method as an efficient and versatile solution for large-scale kernel learning. • We introduce a efficient variant for Nyström approximation of kernel Gram matrices, if the subsequent task is a classification problem. • In that case, the class information can be used to improve the standard landmark selection scheme. • We demonstrate the performance improvement and provide algorithmic details. [ABSTRACT FROM AUTHOR]

To solve the problem of high computational complexity and the lack of local similarity information in constructing similarity matrix, an algorithm combining intrinsic dimension and local tangent space (IDLTS) for manifold spectral clustering image segmentation is proposed. Firstly, considering the manifold structure of image feature space, local linear reconstruction in manifold learning is introduced, and the local tangent spatial similarity of image data is obtained. Secondly, performing the local PCA (Pincipal Components Analysis) in the K-nearest neighbor region of data points, the relationship between intrinsic dimensions of image data is calculated. Combining it with the local tangent spatial similarity, the similarity function and its related similarity matrix of the spectral clustering can be constructed. Thirdly, by sampling points and sampling points, as well as sampling points and non-sampling points, two similarity matrices are constructed with Nyström approximation strategy and used to approximate the eigenvectors for image segmentation. Finally the IDLTS manifold spectral clustering image segmentation is accomplished based on the constructed k principal eigenvectors. Berkeley Segmentation Dataset and eight evaluation metrics are selected to compare the proposed algorithm with some existing image segmentation algorithms. Experimental results show that the IDLTS has good performance in terms of segmentation accuracy and time consumption. [ABSTRACT FROM AUTHOR]

Clustering mixed type data is important for the areas such as knowledge discovery and machine learning. Although many clustering algorithms have been developed for mixed type data, clustering mixed type data is still a challenging task. The challenges mainly come from the fact that the numerical attributes and categorical attributes of mixed type data are not in the same space. Most of the mixed data clustering methods handle the two types of attributes separately. The gap between the numerical attributes and categorical attributes is not handled very well. To handle the above issues, we expand the space structure representation scheme for categorical data to mixed type data. In the new scheme, all the attributes of the mixed type data are expressed as the numerical type, which is in a Euclidean space. In addition, we propose an accelerated approximate space structure based on the Nyström method, which reduces the time cost and memory cost of constructing a space structure. We then propose general frameworks based on the space structure data (SBM) and accelerated approximate space structure (Ap-SBM) for mixed type data clustering. Experimental analyses reflect the ability of the space structure to express the original mixed type data and the ability of the accelerated approximate space structure to express the space structure. The experimental results on thirteen mixed type data sets from UCI show superiority of the proposed frameworks compared with the other six representative mixed type data clustering algorithms. [ABSTRACT FROM AUTHOR]

The spectral clustering method has notable advantages in segmentation. But the high computational complexity and time consuming limit its application in large-scale and dense airborne Light Detection and Ranging (LiDAR) point cloud data. We proposed the Nyström-based spectral clustering (NSC) algorithm to decrease the computational burden. This novel NSC method showed accurate and rapid in individual tree segmentation using point cloud data. The K-nearest neighbour-based sampling (KNNS) was proposed for the Nyström approximation of voxels to improve the efficiency. The NSC algorithm showed good performance for 32 plots in China and Europe. The overall matching rate and extraction rate of proposed algorithm reached 69% and 103%. For all trees located by Global Navigation Satellite System (GNSS) calibrated tape-measures, the tree height regression of the matching results showed an value of 0.88 and a relative root mean square error (RMSE) of 5.97%. For all trees located by GNSS calibrated total-station measures, the values were 0.89 and 4.49%. The method also showed good performance in a benchmark dataset with an improvement of 7% for the average matching rate. The results demonstrate that the proposed NSC algorithm provides an accurate individual tree segmentation and parameter estimation using airborne LiDAR point cloud data.

Spectral clustering, a prominent unsupervised machine learning method, involves a critical task of constructing a similarity matrix. In existing approaches, this matrix is either computed once for all or updated alternatively. However, the former struggles to capture comprehensive relationships among data points, and the latter is often impractical for large-scale problems. This study introduces a new clustering framework with self-guidance and a block diagonal representation, retaining valuable information from previous cycles. To our knowledge, this is the first application of such a framework to spectral clustering, with a key distinction being the reclassification of samples in each cycle. To reduce computational overhead, we employ a block diagonal representation with Nyström approximation for constructing the similarity matrix. Theoretical results justify the rationality of approximate computations in spectral clustering. Comprehensive experiments on benchmark datasets demonstrate the superiority of our proposed algorithms over state-of-the-art methods for large-scale clustering. Notably, our framework has the potential to enhance clustering algorithms, performing well even with a randomly chosen initial guess. • First, we propose a restarted framework for large-scale spectral clustering. More precisely, we reclassify the samples to construct a new similarity matrix according to the clustering information just obtained, and run the spectral clustering method from scratch. We call this strategy restarting. • Second, to release the computation overhead and storage requirement for large-scale problems, we introduce a block diagonal representation for constructing the similarity matrix. More precisely, we make use of a block-diagonal similarity kernel matrix A, and the between cluster affinities are all zeros in the proposed method. • Third, a common disadvantage of the spectral embedding with spectral rotation method is the heavy workload for computing the clustering indicator matrix. Based on the correlation between vectors, we propose a new scheme for updating the clustering indicator matrix efficiently during cycles. [ABSTRACT FROM AUTHOR]

Dictionary learning is an important sparse representation algorithm which has been widely used in machine learning and artificial intelligence. However, for massive data in the big data era, classical dictionary learning algorithms are computationally expensive and even can be infeasible. To overcome this difficulty, we propose new dictionary learning methods based on randomized algorithms. The contributions of this work are as follows. First, we find that dictionary matrix is often numerically low-rank. Based on this property, we apply randomized singular value decomposition (RSVD) to the dictionary matrix, and propose a randomized algorithm for linear dictionary learning. Compared with the classical K-SVD algorithm, an advantage is that one can update all the elements of the dictionary matrix simultaneously. Second, to the best of our knowledge, there are few theoretical results on why one can solve the involved matrix computation problems inexactly in dictionary learning. To fill-in this gap, we show the rationality of this randomized algorithm with inexact solving, from a matrix perturbation analysis point of view. Third, based on the numerically low-rank property and Nyström approximation of the kernel matrix, we propose a randomized kernel dictionary learning algorithm, and establish the distance between the exact solution and the computed solution, to show the effectiveness of the proposed randomized kernel dictionary learning algorithm. Fourth, we propose an efficient scheme for the testing stage in kernel dictionary learning. By using this strategy, there is no need to form nor store kernel matrices explicitly both in the training and the testing stages. Comprehensive numerical experiments are performed on some real-world data sets. Numerical results demonstrate the rationality of our strategies, and show that the proposed algorithms are much efficient than some state-of-the-art dictionary learning algorithms. The MATLAB codes of the proposed algorithms are publicly available from https://github.com/Jiali-yang/RALDL_RAKDL. [ABSTRACT FROM AUTHOR]

As the state-of-the-art technology of Bayesian inference, based on low-dimensional principal components analysis (PCA) subspace inference methods can provide approximately accurate predictive distribution and well calibrated uncertainty. However, the main problem of PCA method is that it is a linear subspace feature extractor, and it cannot effectively represent the nonlinearly high-dimensional parameter space of deep neural networks (DNNs). Firstly, in this paper, in order to solve the main problem of the linear characteristics of PCA in high-dimensional space, we apply kernel PCA to extract higher-order statistical information in parameter space of DNNs. Secondly, to improve the efficiency of subsequent computation, we propose a strictly ordered incremental kernel PCA (InKPCA) subspace of parameter space within stochastic gradient descent (SGD) trajectories. In the proposed InKPCA subspace, we employ two approximation inference methods: elliptical slice sampling (ESS) and variational inference (VI). Finally, to further improve the memory efficiency of computing the kernel matrix, we apply Nyström approximation to determine the suitable size of subsets in the original datasets. The novelty of this paper is that it is the first time to apply the proposed InKPCA subspace with Nyström approximation for Bayesian inference in DNNs, and the results show that it can produce more accurate predictions and well-calibrated predictive uncertainty in regression and classification tasks of deep learning.

This paper presents techniques to improve the prediction accuracy of approximation methods used in Gaussian process regression models. Conventional methods such as Nyström and subset of data methods rely on low-rank approximations to the kernel matrix derived from a set of representative data points. Prediction accuracy suffers when the number of representative points is small or when the length scale is small. The techniques proposed here augment the set of representative points with neighbors of each test input to improve accuracy. Our approach leverages the general structure of the problem through the low-rank approximation and improves its accuracy further by exploiting locality at each test input. Computations involving neighbor points are cast as updates to the base approximation which result in significant savings. To ensure numerical stability, prediction is done via orthogonal projection onto the subspace of the kernel approximation derived from the augmented set. Experiments on synthetic and real datasets show that our approach is robust with respect to changes in length scale and matches the prediction accuracy of the full kernel matrix while using fewer points for kernel approximation. This results in faster and more accurate predictions compared to conventional methods. [ABSTRACT FROM AUTHOR]

Kernel methods provide an elegant framework for developing nonlinear learning algorithms from simple linear methods. Though these methods have superior empirical performance in several real data applications, their usefulness is inhibited by the significant computational burden incurred in large sample situations. Various approximation schemes have been proposed in the literature to alleviate these computational issues, and the approximate kernel machines are shown to retain the empirical performance. However, the theoretical properties of these approximate kernel machines are less well understood. In this work, we theoretically study the trade-off between computational complexity and statistical accuracy in Nyström approximate kernel principal component analysis (KPCA), wherein we show that the Nyström approximate KPCA matches the statistical performance of (nonapproximate) KPCA while remaining computationally beneficial. Additionally, we show that Nyström approximate KPCA outperforms the statistical behavior of another popular approximation scheme, the random feature approximation, when applied to KPCA. [ABSTRACT FROM AUTHOR]

The kernel conjugate gradient (KCG) algorithms have been proposed to improve the convergence rate and the filtering accuracy of kernel adaptive filters (KAFs) efficiently. However, sparsification is necessary in the KCG algorithms to curb the growth of network structure for online applications. To this end, a novel online kernel conjugate gradient algorithm under the mean square error criterion is proposed to approximate the kernel matrix in KAFs by combining k-means sampling into the Nystrom method in a fixed-dimensional feature space, namely a Nystrom kernel conjugate gradient algorithm based on k-means sampling (NysKCG-KM). The approximation accuracy of the kernel matrix as well as the filtering performance of NysKCG-KM are therefore guaranteed by k-means sampling. The proposed NysKCG-KM with no requirement of sparsification can achieve dramatically better filtering accuracy than the kernel least mean square with sparsification, and approach the filtering accuracy of the kernel recursive least squares with sparsification. Monte Carlo simulations using both the synthetic and real-world data validate the superiorities of the proposed NysKCG-KM.

The spectral clustering method has notable advantages in segmentation. But the high computational complexity and time consuming limit its application in large-scale and dense airborne Light Detection and Ranging (LiDAR) point cloud data. We proposed the Nyström-based spectral clustering (NSC) algorithm to decrease the computational burden. This novel NSC method showed accurate and rapid in individual tree segmentation using point cloud data. The K-nearest neighbour-based sampling (KNNS) was proposed for the Nyström approximation of voxels to improve the efficiency. The NSC algorithm showed good performance for 32 plots in China and Europe. The overall matching rate and extraction rate of proposed algorithm reached 69% and 103%. For all trees located by Global Navigation Satellite System (GNSS) calibrated tape-measures, the tree height regression of the matching results showed an value of 0.88 and a relative root mean square error (RMSE) of 5.97%. For all trees located by GNSS calibrated total-station measures, the values were 0.89 and 4.49%. The method also showed good performance in a benchmark dataset with an improvement of 7% for the average matching rate. The results demonstrate that the proposed NSC algorithm provides an accurate individual tree segmentation and parameter estimation using airborne LiDAR point cloud data. [ABSTRACT FROM AUTHOR]

Process monitoring is essential and important strategy for ensuring process safety and product quality. However, due to the nonlinear characteristics and multiple working conditions in process industries, the traditional process monitoring method cannot be effectively applied. Therefore, we propose a novel process monitoring framework, termed as mixture enhanced kernel canonical correlation analysis framework (M-NAKCCA). The innovations and advantages of M-NAKCCA are as follows: 1). The traditional CCA method is re-boosted as a new method, M-NAKCCA, to better nonlinear fault detection. Also, a matter-element model (MEm) is assimilated into M-NAKCCA to make the information more refined. 2). To overcome the curse of dimensionality that usually occurs in the high-dimensional dataset, M-NAKCCA uses the Nyström approximation technology to compress the kernel matrix. Moreover, the T2 control chart is reconstructed and the corresponding control upper limit is re-configured to improve the method sensitivity and to better the fault detection performance. 3). The proposed M-NAKCCA framework is firstly used to monitor a wastewater treatment plant (WWTP) and chemical plant with diverse process behaviors. The experimental results showed that the M-NAKCCA framework achieved the best performance for both of case studies. [ABSTRACT FROM AUTHOR]

In the present paper we consider discrete versions of the modified projection methods for solving a Urysohn integral equation with a kernel of the type of Green’s function. For r ≥ 0, a space of piecewise polynomials of degree ≤ r with respect to an uniform partition is chosen to be the approximating space. We define a discrete orthogonal projection onto this space and replace the Urysohn integral operator by a Nyström approximation. The order of convergence which we obtain for the discrete version indicates the choice of numerical quadrature which preserves the orders of convergence in the continuous modified projection methods. Numerical results are given for a specific example.

This paper is concerned with the computational efficient nonlinear analysis of phasor measurement unit data and presents a Nyström principal components analysis-based algorithm for events detection and localization in an electrical power system. Based on the properly chosen sample subset of every moving window data, the Nyström approximation is carried out to obtain the principal eigenvalues and related eigenvectors of a mapped kernel matrix. Then, the T2 statistic is constructed to detect the abnormal states of an electrical power system. In addition, the contribution of each variable to the T2 statistic is derived to determine the location of the fault bus. Compared with the previous works, the novel version proposed in this paper efficiently reduces the computational burden, and accurately locates the fault bus. Computer simulations using both realistic data, collected from the China power system, and simulated voltage and phase-angle data, validate the reliability of the proposed algorithm.

Approximate solutions of Urysohn integral equations using projection methods involve integrals which need to be evaluated using a numerical quadrature formula. It gives rise to the discrete versions of the projection methods. For r ≥ 1, a space of piecewise polynomials of degree ≤ r − 1 with respect to an uniform partition is chosen to be the approximating space and the projection is chosen to be the interpolatory projection at r Gauss points. Asymptotic expansion for the iterated modified projection solution is available in literature. In this paper, we obtain an asymptotic expansion for the discrete iterated modified projection solution and use Richardson extrapolation to improve the order of convergence. Our results indicate a choice of a numerical quadrature which preserves the order of convergence in the continuous case. Numerical results are given for a specific example. [ABSTRACT FROM AUTHOR]

The performance of most angle estimation system degrades when the signal attributes coherency coupled with the high computational burden of the preprocessing technique. This paper addresses the issue of the computational burden of the coherent angle estimation for the bistatic multiple-input multiple-output (MIMO) radar. A modified spatial smoothing technique is initially developed by ensuring the generation of a lower rank kernel matrix of the decorrelated signal via a Nyström approach. Then the formed data matrix is subjected to the shift-invariance technique where the automatic pairing of the angles is estimated without loss of the virtual aperture. Hence, in addition to significantly reducing the computational complexity, the proposed method presents an improved performance against existing techniques verifiable by simulation results. [ABSTRACT FROM AUTHOR]

• Adopting Invariant Kernel Transfer Learning for sparse models. • Nyström based Basis Transfer for performance improvements by means of prediction and computational time. • A variety of experimental results is provided showing the efficiency of the proposed approach. Transfer learning is focused on the reuse of supervised learning models in a new context. Prominent applications can be found in robotics, image processing or web mining. In these fields, the learning scenarios are naturally changing but often remain related to each other motivating the reuse of existing supervised models. Current transfer learning models are neither sparse nor interpretable. Sparsity is very desirable if the methods have to be used in technically limited environments and interpretability is getting more critical due to privacy regulations. In this work, we propose two transfer learning extensions integrated into the sparse and interpretable probabilistic classification vector machine. They are compared to standard benchmarks in the field and show their relevance either by sparsity or performance improvements. [ABSTRACT FROM AUTHOR]

In the present paper we consider discrete versions of the modified projection methods for solving a Urysohn integral equation with a kernel of the type of Green’s function. For r ≥ 0, a space of piecewise polynomials of degree ≤ r with respect to an uniform partition is chosen to be the approximating space. We define a discrete orthogonal projection onto this space and replace the Urysohn integral operator by a Nyström approximation. The order of convergence which we obtain for the discrete version indicates the choice of numerical quadrature which preserves the orders of convergence in the continuous modified projection methods. Numerical results are given for a specific example. [ABSTRACT FROM AUTHOR]

The Nyström method is a popular technique that uses a small number of landmark points to compute a fixed-rank approximation of large kernel matrices that arise in machine learning problems. In practice, to ensure high quality approximations, the number of landmark points is chosen to be greater than the target rank. However, for simplicity the standard Nyström method uses a sub-optimal procedure for rank reduction. In this paper, we examine the drawbacks of the standard Nyström method in terms of poor performance and lack of theoretical guarantees. To address these issues, we present an efficient modification for generating improved fixed-rank Nyström approximations. Theoretical analysis and numerical experiments are provided to demonstrate the advantages of the modified method over the standard Nyström method. Overall, the aim of this paper is to convince researchers to use the modified method, as it has nearly identical computational complexity, is easy to code, has greatly improved accuracy in many cases, and is optimal in a sense that we make precise. [ABSTRACT FROM AUTHOR]

We propose an efficient spectral clustering method for large-scale data. The main idea in our method consists of employing random Fourier features to explicitly represent data in kernel space. The complexity of spectral clustering thus is shown lower than existing Nyström approximations on large-scale data. With ${m}$ training points from a total of ${n}$ data points, Nyström method requires ${O(nmd+m^{3}+nm^{2})}$ operations, where ${d}$ is the input dimension. In contrast, our proposed method requires ${O(nDd+D^{3}+n'D^{2})}$ , where ${n}'$ is the number of data points needed until convergence and ${D}$ is the kernel mapped dimension. In large-scale datasets where ${n' \ll n}$ hold true, our explicitly mapping method can significantly speed up eigenvector approximation and benefit prediction speed in spectral clustering. For instance, on MNIST (60 000 data points), the proposed method is similar in clustering accuracy to Nyström methods while its speed is twice as fast as Nyström. [ABSTRACT FROM AUTHOR]

Abstract Indefinite similarity measures can be frequently found in bio-informatics by means of alignment scores, but are also common in other fields like shape measures in image retrieval. Lacking an underlying vector space, the data are given as pairwise similarities only. The few algorithms available for such data do not scale to larger datasets. Focusing on probabilistic batch classifiers, the Indefinite Kernel Fisher Discriminant (iKFD) and the Probabilistic Classification Vector Machine (PCVM) are both effective algorithms for this type of data but, with cubic complexity. Here we propose an extension of iKFD and PCVM such that linear runtime and memory complexity is achieved for low rank indefinite kernels. Employing the Nyström approximation for indefinite kernels, we also propose a new almost parameter free approach to identify the landmarks, restricted to a supervised learning problem. Evaluations at several larger similarity data from various domains show that the proposed methods provides similar generalization capabilities while being easier to parametrize and substantially faster for large scale data. [ABSTRACT FROM AUTHOR]

Let X = X ∪ Z be a data set in ℝ D , where X is the training set and Z is the test one. Many unsupervised learning algorithms based on kernel methods have been developed to provide dimensionality reduction (DR) embedding for a given training set Φ : X → ℝ d (d ≪ D) that maps the high-dimensional data X to its low-dimensional feature representation Y = Φ (X). However, these algorithms do not straightforwardly produce DR of the test set Z. An out-of-sample extension method provides DR of Z using an extension of the existent embedding Φ , instead of re-computing the DR embedding for the whole set X. Among various out-of-sample DR extension methods, those based on Nyström approximation are very attractive. Many papers have developed such out-of-extension algorithms and shown their validity by numerical experiments. However, the mathematical theory for the DR extension still need further consideration. Utilizing the reproducing kernel Hilbert space (RKHS) theory, this paper develops a preliminary mathematical analysis on the out-of-sample DR extension operators. It treats an out-of-sample DR extension operator as an extension of the identity on the RKHS defined on X. Then the Nyström-type DR extension turns out to be an orthogonal projection. In the paper, we also present the conditions for the exact DR extension and give the estimate for the error of the extension. [ABSTRACT FROM AUTHOR]

Approximate solutions of linear and nonlinear integral equations using methods related to an interpolatory projection involve many integrals which need to be evaluated using a numerical quadrature formula. In this paper, we consider discrete versions of the modified projection method and of the iterated modified projection method for solution of a Urysohn integral equation with a smooth kernel. For r ≥ 1 , a space of piecewise polynomials of degree ≤ r − 1 with respect to an uniform partition is chosen to be the approximating space and the projection is chosen to be the interpolatory projection at r Gauss points. The orders of convergence which we obtain for these discrete versions indicate the choice of numerical quadrature which preserves the orders of convergence. Numerical results are given for a specific example. [ABSTRACT FROM AUTHOR]

Spectral clustering suffers from a scalability problem in both memory usage and computational time when the number of data instances N is large. To solve this issue, we present a fast spectral clustering algorithm able to effectively handle millions of datapoints at a desktop PC scale. The proposed technique relies on a kernel-based formulation of the spectral clustering problem, also known as kernel spectral clustering. In this framework, the Nyström approximation of the feature map of size m , with m ≪ N , is used to solve the primal optimization problem. This leads to a reduction of time complexity from O ( N 3 ) to O ( mN ) and space complexity from O ( N 2 ) to O ( mN ). The effectiveness of the proposed algorithm in terms of computational efficiency and clustering quality is illustrated on several datasets. [ABSTRACT FROM AUTHOR]

Engineers widely use Gaussian process regression framework to construct surrogate models aimed to replace computationally expensive physical models while exploring design space. Thanks to Gaussian process properties we can use both samples generated by a high fidelity function (an expensive and accurate representation of a physical phenomenon) and a low fidelity function (a cheap and coarse approximation of the same physical phenomenon) while constructing a surrogate model. However, if samples sizes are more than few thousands of points, computational costs of the Gaussian process regression become prohibitive both in case of learning and in case of prediction calculation. We propose two approaches to circumvent this computational burden: one approach is based on the Nyström approximation of sample covariance matrices and another is based on an intelligent usage of a blackbox that can evaluate a low fidelity function on the fly at any point of a design space. We examine performance of the proposed approaches using a number of artificial and real problems, including engineering optimization of a rotating disk shape. [ABSTRACT FROM AUTHOR]

We provide an error bound for the popular Nyström-approximated eigenvectors of the Normalized Cuts (NCut) out-of-sample problem. We then extend our approach to determine the size of training set given a tolerance of approximation error. First, we show that the Nyström-based eigenfunction approximation is identical to the eigensystem approximation of two matrices. We then proceed to study the expected error of matrix approximation. The lower bound on sum of squared singular values of a specific matrix is proposed. Such singular values have a strong relationship to the cosines of principal angles in matrix perturbation theory. The sum of squared singular values is therefore selected to measure the error of eigenvector approximations. From our analysis, we give the training size bound for a fixed approximation error, i.e., at most how many points are required in training set with a desired error in hand. Experiments on various datasets verify the performance of error bound analysis and training size determination. [ABSTRACT FROM AUTHOR]

We propose an incremental spectral clustering method for stream data clustering and apply it to stream image segmentation. The main idea in our work consists of generating the data points in the kernel space by Fastfood features and iteratively calculating the eigendecomposition of data. Compared with the popular Nyström-based approximation, our work accesses each data point only once while Nyström, in particular the sampling scheme, will go through the entire dataset first and calculate the embeddings of data points with a second visit. As a result, our method is able to learn data partitions incrementally and improve eigenvector approximation with more and more data seen from a stream. By contrast, the performance of the standard Nyström is fixed when the sample set is selected. Experimental results show the superiority of our method.

In kernel methods, Nyström approximation is a popular way of calculating out-of-sample extensions and can be further applied to large-scale data clustering and classification tasks. Given a new data point, Nyström employs its empirical affinity vector, k, for calculation. This vector is assumed to be a proper measurement of the similarity between the new point and the training set. In this paper, we suggest replacing the affinity vector by its projections on the leading eigenvectors learned from the training set, i.e., using k*=∑i=1ckTuiui instead, where ui is the i-th eigenvector of the training set and c is the number of eigenvectors used, which is typically equal to the number of classes designed by users. Our work is motivated by the constraints that in kernel space, the kernel-mapped new point should (a) also lie on the unit sphere defined by the Gaussian kernel and (b) generate training set affinity values close to k. These two constraints define a Quadratic Optimization Over a Sphere (QOOS) problem. In this paper, we prove that the projection on the leading eigenvectors, rather than the original affinity vector, is the solution to the QOOS problem. The experimental results show that the proposed replacement of k by k* slightly improves the performance of the Nyström approximation. Compared with other affinity matrix modification methods, our k* obtains comparable or higher clustering performance in terms of accuracy and Normalized Mutual Information (NMI).

In this paper, we describe a method for the determination of a subspace of the feature space in kernel methods, which is suited to large-scale learning problems. Linear model learning in the obtained space corresponds to a nonlinear model learning process in the input space. Since the obtained feature space is determined only by exploiting properties of the training data, this approach can be used for generic nonlinear pattern recognition. That is, nonlinear data mapping can be considered to be a pre-processing step exploiting nonlinear relationships between the training data. Linear techniques can be subsequently applied in the new feature space and, thus, they can model nonlinear properties of the problem at hand. In order to appropriately address the inherent problem of kernel learning methods related to their time and memory complexities, we follow an approximate learning approach. We show that the method can lead to considerable operation speed gains and achieve very good performance. Experimental results verify our analysis. [ABSTRACT FROM AUTHOR]

Universum learning can reflect priori knowledge about application domain and improve classification performances. The kernelized modification of Ho–Kashyap algorithm with squared approximation of the misclassification errors (KMHKS) is an effective learning machine for nonlinearly separable classification problems. While KMHKS only adopts one kernel function, so a multi-kernel classification machine with reduced complexity named Nyström approximation matrix with multiple KMHKSs (NMKMHKS) has been developed. But NMKMHKS has to initialize many parameters and it has not an ability to process noises well. To this end, some scholars propose an improved multi-kernel classification machine with Nyström approximation technique (INMKMHKS). INMKMHKS is based on a new way of generating kernel functions and a new Nyström approximation technique. Related experiments have validated that INMKMHKS possesses five advantages: (1) avoiding the problem of setting too many parameters; (2) keeping comparable space and computational complexities after comparing with NMKMHKS; (3) having a tighter generalization risk bound in terms of Rademacher complexity analysis; (4) possessing an ability to process noises and practical images; (5) a superior recognition can be gotten in a strong correlation between multiple used kernels, which can give a guide advice for choosing kernels. But for traditional multiple kernel learning (MKL), many classification machines including INMKMHKS focus on MKL optimizations, for example, the optimization of model for a MKL. It is difficult for us to find or create a new optimization way now. Indeed, if one pays more attention to data themselves, performance of MKL will also have an improvement. This paper adopts INMKMHKS as a basic learning machine and focuses on data themselves, then it introduces Universum learning into the procedure of INMKMHKS and proposes Universum-based INMKMHKS (Uni-INMKMHKS). The motivation of Uni-INMKMHKS is that it can design a learning machine from data perspective and avoid paying too much attention to MKL optimization which is difficult for scholars to some extent. The contribution of Uni-INMKMHKS is that it has a better recognition than INMKMHKS in average with Universum learning used and inherits the advantages of INMKMHKS simultaneously. [ABSTRACT FROM AUTHOR]

In this paper, we describe an approximate method for reducing the time and memory complexities of the kernel Extreme Learning Machine variants. We show that, by adopting a Nyström-based kernel ELM matrix approximation, we can define an ELM space exploiting properties of the kernel ELM space that can be subsequently used to apply several optimization schemes proposed in the literature for ELM network training. The resulted ELM network can achieve good performance, which is comparable to that of its standard kernel ELM counterpart, while overcoming the time and memory restrictions on kernel ELM algorithms that render their application in large-scale learning problems prohibitive. [ABSTRACT FROM AUTHOR]

Domain specific (dis-)similarity or proximity measures used e.g. in alignment algorithms of sequence data are popular to analyze complicated data objects and to cover domain specific data properties. Without an underlying vector space these data are given as pairwise (dis-)similarities only. The few available methods for such data focus widely on similarities and do not scale to large datasets. Kernel methods are very effective for metric similarity matrices, also at large scale, but costly transformations are necessary starting with non-metric (dis-) similarities. We propose an integrative combination of Nyström approximation, potential double centering and eigenvalue correction to obtain valid kernel matrices at linear costs in the number of samples. By the proposed approach effective kernel approaches become accessible. Experiments with several larger (dis-)similarity datasets show that the proposed method achieves much better runtime performance than the standard strategy while keeping competitive model accuracy. The main contribution is an efficient and accurate technique, to convert (potentially non-metric) large scale dissimilarity matrices into approximated positive semi-definite kernel matrices at linear costs. [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]

Image segmentation methods based on spectral graph theory, although capable of overcoming some of the drawbacks of the so-called 'central'-grouping methods, are computationally expensive and quickly become infeasible to solve as the size of the image grows. As a counter measure, the Nyström approximation allows to extrapolate the complete grouping solution for these methods using only a proportionally smaller set of samples instead of the whole pixels that compose the image. In this correspondence, we further explore the Nyström approximation by taking the concept of 'regions', pixels of the image previously grouped by a central method, to both reduce the computational resources required and provide a finer segmentation of the image by combining the strengths of both methods. We apply the proposed approach to the segmentation of images of burns where we attempt to extract regions that would roughly correspond to the different degrees of the lesion. [ABSTRACT FROM AUTHOR]

Kernelized modification of Ho–Kashyap algorithm with squared approximation of the misclassification errors (KMHKS) is an effective algorithm for nonlinearly separable classification problems. While KMHKS only adopts one kernel function. So a multi-kernel classification machine with reduced complexity named Nyström approximation matrix with Multiple KMHKSs (NMKMHKS) has been developed. But NMKMHKS has to initialize many parameters and has not an ability to deal with noise well. To this end, we propose an improved multi-kernel classification machine with Nyström approximation technique (INMKMHKS). INMKMHKS is based on a new way of generating kernel functions and a new Nyström approximation technique. The contributions of INMKMHKS are that (1) avoiding the problem of setting too many parameters; (2) keeping comparable space and computational complexities after comparing with NMKMHKS; (3) having a tighter generalization risk bound in terms of Rademacher complexity analysis; (4) having a better recognition than NMKMHKS on average; (5) possessing an ability to deal with noise and practical images. [ABSTRACT FROM AUTHOR]