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 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]

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]

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 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]

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]

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]

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]

Multiple Kernel Learning (MKL) has been demonstrated to improve classification performance effectively. But it will cause a large complexity in some large-scale cases. In this paper, we aim to reduce both the time and space complexities of MKL, and thus propose an efficient multi-kernel classification machine based on the Nyström approximation. Firstly, we generate different kernel matrices K p s for given data. Secondly, we apply the Nyström approximation technique into each K p so as to obtain its corresponding approximation matrix K ∼ p . Thirdly, we fuse multiple generated K ∼ p s into the final ensemble matrix G ∼ with one certain heuristic rule. Finally, we select the Kernelized Modification of Ho–Kashyap algorithm with Squared approximation of the misclassification errors (KMHKS) as the incorporated paradigm, and meanwhile apply the G ∼ into KMHKS. In doing so, we propose a multi-kernel classification machine with reduced complexity named Nyström approximation matrix with Multiple KMHKSs (NMKMHKS). The experimental results here validate both the effectiveness and efficiency of the proposed NMKMHKS. The contributions of NMKMHKS are that: (1) compared with the existing MKL, NMKMHKS reduces the computational complexity of finding the solution scale from O ( Mn 3 ) to O ( Mnm 2 ) , where M is the number of kernels, n is the number of training samples, and m is the number of the selected columns from K p . Meanwhile, NMKMHKS reduces the space complexity of storing the kernel matrices from O ( Mn 2 ) to O ( n 2 ) ; (2) compared with the original KMHKS, NMKMHKS improves the classification performance but keeps a comparable space complexity; (3) the better recognition of NMKMHKS can be got in a strong correlation between multiple used K p s; and (4) NMKMHKS has a tighter generalization risk bound in terms of the Rademacher complexity analysis. [ABSTRACT FROM AUTHOR]

Multiple Kernel Discriminant Analysis (MKDA) adopts an ensemble of multiple kernel matrices K i s and is supposed to be more flexible and effective than the original Kernel Discriminant Analysis (KDA). However, with n training samples and p kernel matrices K i s, MKDA employs pn 2 space units for all the K i s in the optimizing process and simultaneously depends on its solving techniques to handle the optimization problem, which would cause a large space and computational complexity and limit the efficiency and applicability. In order to mitigate this problem, this manuscript adopts the Nyström method approximating K i and therefore develops a novel Multiple Nyström-Approximating Kernel Discriminant Analysis (MNKDA). In practice, the proposed MNKDA first adopts m ( ) samples to generate an approximating kernel matrix for each K i and forms an ensemble matrix . Then, MNKDA directly applies the eigenvalue decomposition onto the Nyström-based ensemble matrix G and reformulates the proposed discriminant analysis as an eigenvalue problem. The experimental results show that the proposed method can achieve an effective and efficient performance than the classical MKDA. The advantages of the proposed MNKDA are (1) expressing the formulation as an eigenvalue problem resolution instead of using commercial softwares; (2) decreasing the space complexity from to and mitigating the computational complexity from to ; and (3) providing an alternative multiple kernel learning technique and inheriting the advantage of multiple kernel learning. [ABSTRACT FROM AUTHOR]

Many kernel-based learning algorithms have the computational load scaled with the sample size due to the column size of a full kernel Gram matrix . This article considers the Nyström low-rank approximation. It uses a reduced kernel , which is , consisting of columns (say columns ) randomly drawn from . This approximation takes the form , where is the reduced matrix formed by rows of . Often is much smaller than the sample size resulting in a thin rectangular reduced kernel, and it leads to learning algorithms scaled with the column size . The quality of matrix approximations can be assessed by the closeness of their eigenvalues and eigenvectors. In this article, asymptotic error bounds on eigenvalues and eigenvectors are derived for the Nyström low-rank approximation matrix. [ABSTRACT FROM AUTHOR]

Convergence and conditioning results are presented for the lowest-order member of a family of Nyström methods for arbitrary, exterior, three-dimensional Stokes flow. The flow problem is formulated in terms of a recently introduced two-parameter, weakly singular boundary integral equation of the second kind. In contrast to methods based on product integration, coordinate transformation and singularity subtraction, the family of Nyström methods considered here is based on a local polynomial correction determined by an auxiliary system of moment equations. The polynomial correction is designed to remove the weak singularity in the integral equation and provide control over the approximation error. Here we focus attention on the lowest-order method of the family, whose implementation is especially simple. We outline a convergence theorem for this method and illustrate it with various numerical examples. Our examples show that well-conditioned, accurate approximations can be obtained with reasonable meshes for a range of different geometries. [ABSTRACT FROM AUTHOR]

We consider the numerical approximation of a nonlinear integral operator equation by the Nyström method. We propose a new way of applying this method which leads to a major improvement: We can theoretically attain any desired accuracy while for the classical Nyström, the accuracy is limited by the quadrature error formula. The basic idea behind this new proposition is linearizing the nonlinear equation and discretizing the linearization process after, while the usual approach consists in the opposite. [ABSTRACT FROM AUTHOR]

Abstract: Recently, diverse high quality prototype-based clustering techniques have been developed which can directly deal with data sets given by general pairwise dissimilarities rather than standard Euclidean vectors. Examples include affinity propagation, relational neural gas, or relational generative topographic mapping. Corresponding to the size of the dissimilarity matrix, these techniques scale quadratically with the size of the training set, such that training becomes prohibitive for large data volumes. In this contribution, we investigate two different linear time approximation techniques, patch processing and the Nyström approximation. We apply these approximations to several representative clustering techniques for dissimilarities, where possible, and compare the results for diverse data sets. [Copyright &y& Elsevier]

We derive generalization error (loss) bounds for orthogonal matching pursuit algorithms, starting with kernel matching pursuit and sparse kernel principal components analysis. We propose (to the best of our knowledge) the first loss bound for kernel matching pursuit using a novel application of sample compression and Vapnik-Chervonenkis bounds. For sparse kernel principal components analysis, we find that it can be bounded using a standard sample compression analysis, as the subspace it constructs is a compression scheme. We demonstrate empirically that this bound is tighter than previous state-of-the-art bounds for principal components analysis, which use global and local Rademacher complexities. From this analysis we propose a novel sparse variant of kernel canonical correlation analysis and bound its generalization performance using the results developed in this paper. We conclude with a general technique for designing matching pursuit algorithms for other learning domains. [ABSTRACT FROM PUBLISHER]

Abstract: In this paper, we derive an ensemble method inspired by boosting, a novel Robust Positive semidefinite L-Isomap Ensemble (RPL-IsomapE) approach. Specifically, we first apply a constant-shifting method to yield a symmetric positive semidefinite (SPSD) matrix. For topological stability, we also employ a method for eliminating critical outlier points using the confusion rate of all the data points. Then we align individual Robust Positive semidefinite L-Isomap (RPL-Isomap) solutions in common coordinate system through high dimensional affine transformations. Finally, we combine multiple RPL-Isomap solutions by the weighted averaging procedure according to residual variance to improve the noise-robustness of our method. Our RPL-IsomapE maintains the scalability and the speed of L-Isomap. Experiments on two images data sets and a video data set confirm the promising performance of the proposed RPL-IsomapE. [ABSTRACT FROM AUTHOR]

• A new matrix factorization strategy is designed for Nyström spectral clustering. • Incomplete Cholesky decomposition is introduced to accelerate Nyström approximation. • An efficient Nyström spectral clustering algorithm called ICD-NSC is proposed. • The effectiveness of ICD-NSC is demonstrated by comprehensive experiments. Nyström method can estimate the eigenvectors of a large kernel matrix with the eigenvectors of a small sampled sub-matrix. However, we may encounter two problems when using Nyström method to speed up spectral clustering: one problem is the approximate eigenvectors generated by standard Nyström method are sub-optimal, so they may impair the performance of spectral clustering; another one is the accurate Nyström approximation needs a sufficient number of samples, which will increase the eigen-decomposition cost on the sampled sub-matrix. To solve these problems, this paper proposes an efficient Nyström spectral clustering algorithm using incomplete Cholesky decomposition, in which a new matrix factorization strategy is designed for Nyström spectral clustering to meet the orthogonal constraints, and an efficient eigensolver based on incomplete Cholesky decomposition is developed to accelerate the Nyström approximation. In this way, the obtained approximate orthogonal eigenvectors will help to improve the clustering quality, and the developed eigenvector calculation method will help to reduce the clustering complexity. The experimental results show that the proposed algorithm performs well on many challenging data sets, and it can accomplish more complex clustering tasks with limited computing resources. [ABSTRACT FROM AUTHOR]

In dealing with large data sets, the reduced support vector machine (RSVM) was proposed for the practical objective to overcome some computational difficulties as well as to reduce the model complexity. In this paper, we study the RSVM from the viewpoint of sampling design, its robustness, and the spectral analysis of the reduced kernel. We consider the nonlinear separating surface as a mixture of kernels. Instead of a full model, the RSVM uses a reduced mixture with kernels sampled from certain candidate set. Our main results center on two major themes. One is the robustness of the random subset mixture model. The other is the spectral analysis of the reduced kernel. The robustness is judged by a few criteria as follows: 1) model variation measure; 2) model bias (deviation) between the reduced model and the full model; and 3) test power in distinguishing the reduced model from the full one. For the spectral analysis, we compare the eigenstructures of the full kernel matrix and the approximation kernel matrix. The approximation kernels are generated by uniform random subsets. The small discrepancies between them indicate that the approximation kernels can retain most of the relevant information for learning tasks in the full kernel. We focus on some statistical theory of the reduced set method mainly in the context of the RSVM. The use of a uniform random subset is not limited to the RSVM. This approach can act as a supplemental algorithm on top of a basic optimization algorithm, wherein the actual optimization takes place on the subset-approximated data. The statistical properties discussed in this paper are still valid. [ABSTRACT FROM AUTHOR]

Abstract: Kernel based methods suffer from exceeding time and memory requirements when applied on large datasets since the involved optimization problems typically scale polynomially in the number of data samples. As a remedy, some least squares methods on one hand only reduce the number of parameters (for fast training), on the other hand only work on a reduced set (for fast evaluation). Departing from the Nyström based feature approximation, via the fixed-size LS-SVM model, we propose a general regression framework, based on restriction of the search space to a subspace and a particular choice of basis vectors in feature space. In the general model both reduction aspects are unified and become explicit model choices. This allows to accommodate kernel Partial Least Squares and kernel Canonical Correlation analysis for regression with a sparse representation, which makes them applicable to large data sets, with little loss in accuracy. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

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 = 1 c k T u i u i instead, where u i 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). [ABSTRACT FROM AUTHOR]

Spectral clustering algorithms have been shown to be more effective in finding clusters than some traditional algorithms, such as k-means. However, spectral clustering suffers from a scalability problem in both memory use and computational time when the size of a data set is large. To perform clustering on large data sets, we investigate two representative ways of approximating the dense similarity matrix. We compare one approach by sparsifying the matrix with another by the Nyström method. We then pick the strategy of sparsifying the matrix via retaining nearest neighbors and investigate its parallelization. We parallelize both memory use and computation on distributed computers. Through an empirical study on a document data set of 193,844 instances and a photo data set of 2,121,863, we show that our parallel algorithm can effectively handle large problems. [ABSTRACT FROM AUTHOR]