On the convergence of the partial least squares path modeling algorithm

This paper adds to an important aspect of Partial Least Squares (PLS) path modeling, namely the convergence of the iterative PLS path modeling algorithm. Whilst conventional wisdom says that PLS always converges in practice, there is no formal proof for path models with more than two blocks of manifest variables. This paper presents six cases of non-convergence of the PLS path modeling algorithm. These cases were estimated using Mode A combined with the factorial scheme or the path weighting scheme, which are two popular options of the algorithm. As a conclusion, efforts to come to a proof of convergence under these schemes can be abandoned, and users of PLS should triangulate their estimation results.     

Local convergence of a secant type method for solving least squares problems

Local convergence of a secant type iterative method for approximating a solution of nonlinear least squares problems is investigated in this paper. The radius of convergence is determined as well as usable error estimates. Numerical examples are also provided.     

Practical alternating least squares for tensor ring decomposition

Tensor ring (TR) decomposition has been widely applied as an effective approach in a variety of applications to discover the hidden low-rank patterns in multidimensional and higher-order data. A well-known method for TR decomposition is the alternating least squares (ALS). However, solving the ALS subproblems often suffers from high cost issue, especially for large-scale tensors. In this paper, we provide two strategies to tackle this issue and design three ALS-based algorithms. Specifically, the first strategy is used to simplify the calculation of the coefficient matrices of the normal equations for the ALS subproblems, which takes full advantage of the structure of the coefficient matrices of the subproblems and hence makes the corresponding algorithm perform much better than the regular ALS method in terms of computing time. The second strategy is to stabilize the ALS subproblems by QR factorizations on TR-cores, and hence the corresponding algorithms are more numerically stable compared with our first algorithm. Extensive numerical experiments on synthetic and real data are given to illustrate and confirm the above results. In addition, we also present the complexity analyses of the proposed algorithms.     

On the consistency of a least squares identification procedure in linear evolution systems

Conditions for the convergence of parameter estimates to the true value applicable in continuous time linear stochastic evolution systems are presented. A special case, continuous time linear stochastic systems with delays, is also considered. A persistent excitation property is proved by control theory methods     

Gamma-convergence and the least squares method

We study the asymptotic behaviour of the sequence of first order equations _tu––a_h(y)_xu=0 by means of the related energies

Blockwise acceleration of alternating least squares for canonical tensor decomposition

The canonical polyadic (CP) decomposition of tensors is one of the most important tensor decompositions. While the well-known alternating least squares (ALS) algorithm is often considered the workhorse algorithm for computing the CP decomposition, it is known to suffer from slow convergence in many cases and various algorithms have been proposed to accelerate it. In this article, we propose a new accelerated ALS algorithm that accelerates ALS in a blockwise manner using a simple momentum-based extrapolation technique and a random perturbation technique. Specifically, our algorithm updates one factor matrix (i.e., block) at a time, as in ALS, with each update consisting of a minimization step that directly reduces the reconstruction error, an extrapolation step that moves the factor matrix along the previous update direction, and a random perturbation step for breaking convergence bottlenecks. Our extrapolation strategy takes a simpler form than the state-of-the-art extrapolation strategies and is easier to implement. Our algorithm has negligible computational overheads relative to ALS and is simple to apply. Empirically, our proposed algorithm shows strong performance as compared to the state-of-the-art acceleration techniques on both simulated and real tensors.     

On the linear convergence of the alternating direction method of multipliers

We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global R-linear convergence of the ADMM for minimizing the sum of any number of convex separable functions, assuming that a certain error bound condition holds true and the dual stepsize is sufficiently small. Such an error bound condition is satisfied for example when the feasible set is a compact polyhedron and the objective function consists of a smooth strictly convex function composed with a linear mapping, and a nonsmooth \(\ell _1\) regularizer. This result implies the linear convergence of the ADMM for contemporary applications such as LASSO without assuming strong convexity of the objective function.     

On the weighting method for mixed least squares–total least squares problems

It is well known that the standard algorithm for the mixed least squares–total least squares (MTLS) problem uses the QR factorization to reduce the original problem into a standard total least squares problem with smaller size, which can be solved based on the singular value decomposition (SVD). In this paper, the MTLS problem is proven to be closely related to a weighted total least squares problem with its error‐free columns multiplied by a large weighting factor. A criterion for choosing the weighting factor is given; and for the sake of stability in solving the MTLS problem, the Cholesky factorization‐based inverse (Cho‐INV) iteration and Rayleigh quotient iteration are also considered. For large‐scale MTLS problems, numerical tests show that Cho‐INV is superior to the standard QR‐SVD method, especially for the case with big gap between the desired and undesired singular values and the case when the coefficient matrix has much more error‐contaminated columns. Rayleigh quotient iteration behaves more efficient than QR‐SVD for most cases and fails occasionally, and in some cases, it converges much faster than Cho‐INV but still less efficient due to its higher computation cost.     

Convergence conditions of the least squares method

Least squares estimation of parameters is considered. Sufficient conditions of strong consistency are obtained for a regression model in the presence of random errors.Kiev University. Translated from Vychislitel'naya i Prikladnaya Matematika, No. 75, pp. 38–43, 1991.     

200 years of least squares method

---

200 years of least squares method

---

     

Minimax estimation and the least squares method

This paper is devoted to the problem of minimax estimation of parameters in linear regression models with uncertain second order statistics. The solution to the problem is shown to be the least squares estimator corresponding to the least favourable matrix of the second moments. This allows us to construct a new algorithm for minimax estimation closely connected with the least squares method. As an example, we consider the problem of polynomial regression introduced by A. N. Kolmogorov     

On polynomial approximation in the uniform norm by the discrete least squares method

The discrete least squares method is convenient for computing polynomial approximations to functions. We investigate the possibility of using this method to obtain polynomial approximants good in the uniform norm, and find that for a given set ofm nodes, the degreen of the approximating polynomial should be selected so that there is a subset ofn+1 nodes which are close ton+1 Fejér points for the curve. Numerical examples are presented.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041.     

Exponential convergence in a Galerkin least squares hp-FEM for Stokes flow

A stabilized hp-finite element method (FEM) of Galerkin leastsquares (GLS) type is analysed for the Stokes equations in polygonaldomains. Contrary to the standard Galerkin FEM, the GLSFEM admitsthe implementationally attractive equal-order interpolationin the velocity and the pressure. In conjunction with geometricallyrefined meshes and linearly increasing approximation ordersit is shown that the hp-GLSFEM leads to exponential rates ofconvergence for solutions exhibiting singularities near corners.To obtain this result a novel hp-interpolation result is provedthat allows the approximation of pressure functions in certainweighted Sobolev spaces in a conforming way and at exponentialrates of convergence on geometric meshes. Received 6 June 1999. Accepted 14 March 2000.     

An extension of the method of least squares

The standard method of least squares assumes that there is a linear relationship relating two variables, only one of which has an error in it. A discussion of the validity of this assumption leads to the desirability of a technique which applies to the more general situation where both variables are subject to error. This includes relating the relevant statistical distance to be minimized to the Euclidean distance. The corresponding statistical formulae are derived, and simple comparisons are then made for various ranges of the statistical parameters.     

The accuracy of the method of least squares

A generalization of the method of least squares is considered. Asymptotic properties of the estimates obtained with the help of the method in the case of stationary noise are studied. Bibliography:1 title. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 228, 1996, pp. 294–299     

Development of the collocations and least squares method

We propose and implement new, more general versions of the method of collocations and least squares (the CLS method) and, for a system of linear algebraic equations, an orthogonal method for accelerating the convergence of an iterative solution. The use of the latter method and the proper choice of values of control parameters, based on the results of investigating the dependence of the properties of the CLS method on these parameters, as well as some other improvements of the CLS method suggested in this paper, allow one to solve numerically problems for Navier-Stokes equations in a reasonable time using a single-processor computer even for grids as large as 1280 × 1280. In this case, the total number of unknown variables is ～ 25 · 10⁶. The numerical results for the problem of the lid-driven cavity flow of a viscous fluid are in good agreement with known results of other authors, including those obtained by means of schemes of higher approximation order with a small artificial viscosity. This and some other facts prove that the new versions of the CLS method make it possible to obtain an approximate solution with high accuracy.     

Sparse linear problems of the least squares method

One gives a survey of the direct method of solving large sparse diverse overdetermined linear systems of full column rank in the least squares sense. The survey covers practically all investigations on this topic, published in the seventies and in the beginning of the eighties.Translated from Itogi Nauki i Tekhniki, Seriya Matematicheskii Analiz, Vol. 23, pp. 219–285, 1985.     

CP decomposition for tensors via alternating least squares with QR decomposition

The CP tensor decomposition is used in applications such as machine learning and signal processing to discover latent low-rank structure in multidimensional data. Computing a CP decomposition via an alternating least squares (ALS) method reduces the problem to several linear least squares problems. The standard way to solve these linear least squares subproblems is to use the normal equations, which inherit special tensor structure that can be exploited for computational efficiency. However, the normal equations are sensitive to numerical ill-conditioning, which can compromise the results of the decomposition. In this paper, we develop versions of the CP-ALS algorithm using the QR decomposition and the singular value decomposition, which are more numerically stable than the normal equations, to solve the linear least squares problems. Our algorithms utilize the tensor structure of the CP-ALS subproblems efficiently, have the same complexity as the standard CP-ALS algorithm when the input is dense and the rank is small, and are shown via examples to produce more stable results when ill-conditioning is present. Our MATLAB implementation achieves the same running time as the standard algorithm for small ranks, and we show that the new methods can obtain lower approximation error.