The Nystrom Method

Perhaps the most well known algorithm specific out-of-sample estimation method is that of Bengio et al. [6] where the problem of spectral dimensionality reduction is phrased within a kernel framework so that the Nystrom technique can be used to perform the out-of-sample extension. 

In general terms, a symmetric matrix F is formed from a kernel function K such that Fj = AT(Xj, Xj). There then exists an eigenvector and eigenvalue pair, (u, k,), such that Fuj = XjUj. The low-dimensional embedding, y, of x is then given by 

The continuous version of the double centring equation (Eq. 2.4) gives rise to the normalised kernel for MDS  

The method to extend Isomap to incorporate a new point proposed in [6] does not explicitly recompute the geodesic distances with respect to the new point. Rather, the geodesic distances cj) (a, b) over the original data X are used and the j-th co-ordinate of the low-dimensional representation of an unseen point x is given by 

Laplacian Eigenmaps relies on the use of a kernel to define point wise similarities and as such this initial kernel is represented by K. With this in place, the extend kernel can be formed as  

---

As discussed above, the eigendecomposition is often the most computationally expensive step. There is therefore areal need to provide solutions that help overcome the computational bottleneck associated with performing eigendecomposition. Perhaps the most widely used method to help reduce the computational complexity of the eigendecomposition is the Nystrom method [11-13]. 

Originally the NystrCm method was introduced as a method for numerical integration used to approximate eigenfunction solutions [14]. However, in recent years the method has been leveraged to provide a means of improving the performance of kernel machines [ 13]. As such, the Nystrom method used for spectral dimensionality reduction exploits the fact that spectral dimensionality reduction techniques can be phrased as kernel problems [15]. The basic premise of the Nystrom method is to select a small subset of the n x n matrix and then approximate the remaining subset of the data. As noted in [11], it is useful to describe the Nystrom method in terms of matrix completion. 

WiUiams, C.K.I., Seeger, M. Using the Nystrom method to speed up kernel machines. In Advances in Neural Information Processing Systems 13 Proceedings of the 2001 Conference (NIPS), pp. 682-688 (2001)... 

Kumar, S., Mohti, M., Talwalkar, A. Samping techniques for the nystrom method. Journal of Machine Learning Research 13(1), 981-1006 (2012)... 

In ref. 143 the authors develop a third-order 3-stage diagonally implicit Runge-Kutta-Nystrom method embedded in fourth-order 4-stage for solving special second-order initial value problems. The obtained method has been developed in order to have minimal local truncation error as well as the last row of the coefficient matrix is equal to the vector output. The authors also study the stability of the method. The new proposed method is illustrated via a set of test problems. 

In ref 156 the author studies the stability properties of a family of exponentially fitted Runge-Kutta-Nystrom methods. More specifically the author investigates the P-stability which is a very important property usually required for the numerical solution of stiff oscillatory second-order initial value problems. In this paper P-stable exponentially fitted Runge-Kutta-Nystrom methods with arbitrary high order are developed. The results of this paper are proved based on a S5unmetry argument. 

In ref 164 new and elficient trigonometrically-fitted adapted Runge-Kutta-Nystrom methods for the numerical solution of perturbed oscillators are obtained. These methods combine the benefits of trigonometrically-fitted methods with adapted Runge-Kutta-Nystrom methods. The necessary and sufficient order conditions for these new methods are produced based on the linear-operator theory. 

In ref 171 new Runge-Kutta-Nystrom methods for the numerical solution of periodic initial value problems are obtained. These methods are able to integrate exactly the harmonic oscillator. In this paper the analysis of the production of an embedded 5(3) RKN pair with four stages is presented. 

In ref. 172 a new embedded pair of explicit Runge-Kutta-Nystrom (RKN) methods adapted to the numerical solution of general perturbed oscillators is produced. This pair is based on the methods developed by Franco.These methods can be used for general problems. It is proved that the embedded methods have algebraic order 4 and 3. 

In ref 174 a new embedded pair of explicit exponentially fitted Runge-Kutta-Nystrom methods is developed. The methods integrate exactly any linear combinations of the functions from the set (exp(/iO,exp(—/it) (ji e ifl or /i e i9I). The new methods have the following characteristics ... 

T. E. Simos and P. S. Williams, A new Runge-Kutta-Nystrom method with phase-lag of order infinity for the numerical solution of the Schrodinger equation, MATCH Commun. Math. Comput. Chem., 2002, 45, 123-137. 

Z. Kalogiratou and T. E. Simos, Construction of trigonometrically and exponentially fitted Runge-Kutta-Nystrom methods for the numerical solution of the SchrSdinger equation and related problems a method of 8th algebraic order, J. Math. Chem., 2002, 31(2), 211-232. 

Hans Van de Vyver, On the generation of P-stable exponentially fitted Runge-Kutta-Nystrom methods by exponentially fitted Runge-Kutta methods. Journal of Computational and Applied Mathematics, 2006, 188, 309-318. 

J. M. Franco, Runge-Kutta-Nystrom methods adapted to the numerical integration of perturbed oscillators, Comput. Phys. Commun., 2002, 147, 770-787. 

Hans Van de Vyver, An embedded exponentially fitted Runge-Kutta-Nystrom method for the numerical solution of orbital problems. New Astronomy, 2006, 11, 577-587. 

In this flow chart is the end-point of integration, is the start-point of integration and NSTEP is the number of steps. The computation of qh zu i = 1(1)3 is based on the Runge-Kutta-Nystrom method of Dormand and Prince 8(7) (see 9-10). 

The Runge-Kutta Kutaa-Nystrom method has better behavior than the Runge-Kutta Butcher method... 

In 52 the author develops a symplectic exponentially fitted modified Runge-Kutta-Nystrom method. The method of development was based on the development of symplectic exponentially fitted modified Runge-Kutta-Ny-strom method by Simos and Vigo-Aguiar. The new method is a two-stage second-order method with FSAL-property (first step as last). 

Phase-lag Analysis of the Runge-Kutta-Nystrom Methods. - For the numerical solution of the problem (129), the m-stage explicit Runge-Kutta-Nystrom (RKN) method shown in Table 6 can be used. Application of this method to the scalar test equation (130) produces the numerical solution... 

Based on the results presented in the relative papers and based on some numerical tests made for this review, the most efficient Runge-Kutta method for specific Schrodinger equations is the one developed by Simos and Williams106 with seven stages while the Runge-Kutta-Nystrom method developed by Simos, Dimas and Sideridis107 gives similar results in accuracy and computational efficiency. 

In [15], [26], [32], [59]-[60], [72] some modified Runge-Kutta or Runge-Kutta-Nystrom methods are constructed. The modification is based on exponential and trigonometric fitting or phase-fitting property. 

In [160] the authors obtained a new fourth algebraic order Rimge Kutta-Nystrom method with vanished phase-lag, amplification error and the first derivatives of the previous properties. More spedlically the authors consider the general form of the Runge-Kutta-Nystrom method... 

In the above seheme if Ci = 0 then we an explicit Runge Kutta Nystrom method. If = 1 and = fc, for j= i then we have an FSAL explicit RKN... 

In [190] the authors studied extended Runge-Kutta-Nystrom methods of the form ... 

In the same formula, h is the step size of the integration and n is the number of steps, i.e. is the approximation of the solution in the point x and Xn = XQ + n h and xq is the initial value point. Using the above methods and based on the theory of phase-lag and amplification error for the Runge-Kutta-Nystrom methods, the authors have derived two fourth algebraic order Runge-Kutta-Nystrom methods with phase-lag of order four and amplification error of order five. For both of methods the authors have obtained the stability regions. The efficiency of the produced methods is proved via numerical experiments. 

In [211] the authors obtained a new embedded 4(3) pair explicit four-stage fourth-order Runge-Kutta-Nystrom (RKN) method to integrate second-order differential equations with oscillating solutions. The proposed method has high phase-lag order with small principal local truncation error coefficient. The authors given the stability analysis of the proposed method. Numerical comparisons of this new obtained method to problems with oscillating and/or periodical behavior of the solution show the efficiency of the method. 

The following (m + l)-stage modified Runge-Kutta-Nystrom method has been introduced in order to solve numerically the above problem ... 

As Aguiar, Simos and Tocino have proved, in order that the Runge-Kutta-Nystrom method defined by (5)-(7) integrates exactly equation (3) with /( j = 0 the coefficients A, B, C, D and C Di of the method must be given by ... 

Case hi = 0. - In the case m = 0, solving the above relations, Aguiar, Simos and Tocino have found the following family of Rimge-Kutta-Nystrom methods with order two ... 

Runge-Kutta-Nystrom Method with FSAL Property. - We give the following definition. 

---