共查询到17条相似文献,搜索用时 0 毫秒
1.
Eugene Tyrtyshnikov 《高等学校计算数学学报(英文版)》2009,2(4):421-426
For an arbitrary tensor (multi-index array) with linear constraints at each direction, it is proved that the factors of any minimal canonical tensor approximation to this tensor satisfy the same linear constraints for the corresponding directions. 相似文献
2.
Alternating least squares (ALS) is often considered the workhorse algorithm for computing the rank‐R canonical tensor approximation, but for certain problems, its convergence can be very slow. The nonlinear conjugate gradient (NCG) method was recently proposed as an alternative to ALS, but the results indicated that NCG is usually not faster than ALS. To improve the convergence speed of NCG, we consider a nonlinearly preconditioned NCG (PNCG) algorithm for computing the rank‐R canonical tensor decomposition. Our approach uses ALS as a nonlinear preconditioner in the NCG algorithm. Alternatively, NCG can be viewed as an acceleration process for ALS. We demonstrate numerically that the convergence acceleration mechanism in PNCG often leads to important pay‐offs for difficult tensor decomposition problems, with convergence that is significantly faster and more robust than for the stand‐alone NCG or ALS algorithms. We consider several approaches for incorporating the nonlinear preconditioner into the NCG algorithm that have been described in the literature previously and have met with success in certain application areas. However, it appears that the nonlinearly PNCG approach has received relatively little attention in the broader community and remains underexplored both theoretically and experimentally. Thus, this paper serves several additional functions, by providing in one place a concise overview of several PNCG variants and their properties that have only been described in a few places scattered throughout the literature, by systematically comparing the performance of these PNCG variants for the tensor decomposition problem, and by drawing further attention to the usefulness of nonlinearly PNCG as a general tool. In addition, we briefly discuss the convergence of the PNCG algorithm. In particular, we obtain a new convergence result for one of the PNCG variants under suitable conditions, building on known convergence results for non‐preconditioned NCG. Copyright © 2014 John Wiley & Sons, Ltd. 相似文献
3.
We present Nesterov‐type acceleration techniques for alternating least squares (ALS) methods applied to canonical tensor decomposition. While Nesterov acceleration turns gradient descent into an optimal first‐order method for convex problems by adding a momentum term with a specific weight sequence, a direct application of this method and weight sequence to ALS results in erratic convergence behavior. This is so because ALS is accelerated instead of gradient descent for our nonconvex problem. Instead, we consider various restart mechanisms and suitable choices of momentum weights that enable effective acceleration. Our extensive empirical results show that the Nesterov‐accelerated ALS methods with restart can be dramatically more efficient than the stand‐alone ALS or Nesterov's accelerated gradient methods, when problems are ill‐conditioned or accurate solutions are desired. The resulting methods perform competitively with or superior to existing acceleration methods for ALS, including ALS acceleration by nonlinear conjugate gradient, nonlinear generalized minimal residual method, or limited‐memory Broyden‐Fletcher‐Goldfarb‐Shanno, and additionally enjoy the benefit of being much easier to implement. We also compare with Nesterov‐type updates where the momentum weight is determined by a line search (LS), which are equivalent or closely related to existing LS methods for ALS. On a large and ill‐conditioned 71×1,000×900 tensor consisting of readings from chemical sensors to track hazardous gases, the restarted Nesterov‐ALS method shows desirable robustness properties and outperforms any of the existing methods we compare with by a large factor. There is clear potential for extending our Nesterov‐type acceleration approach to accelerating other optimization algorithms than ALS applied to other nonconvex problems, such as Tucker tensor decomposition. 相似文献
4.
Numerical multilinear algebra (or called tensor computation), in which instead of matrices and vectors the higher-order tensors
are considered in numerical viewpoint, is a new branch of computational mathematics. Although it is an extension of numerical
linear algebra, it has many essential differences from numerical linear algebra and more difficulties than it. In this paper,
we present a survey on the state of the art knowledge on this topic, which is incomplete, and indicate some new trends for
further research. Our survey also contains a detailed bibliography as its important part. We hope that this new area will
be receiving more attention of more scholars.
相似文献
5.
Michael J. O'Hara 《Numerical Linear Algebra with Applications》2014,21(1):1-12
The problem of symmetric rank‐one approximation of symmetric tensors is important in independent components analysis, also known as blind source separation, as well as polynomial optimization. We derive several perturbative results that are relevant to the well‐posedness of recovering rank‐one structure from approximately‐rank‐one symmetric tensors. We also specialize the analysis of the shifted symmetric higher‐order power method, an algorithm for computing symmetric tensor eigenvectors, to approximately‐rank‐one symmetric tensors. Copyright © 2012 John Wiley & Sons, Ltd. 相似文献
6.
General results giving approximate bias for nonlinear models with constrained parameters are applied to bilinear models in ANOVA framework, called biadditive models. Known results on the information matrix and the asymptotic variance matrix of the parameters are summarized, and the Jacobians and Hessians of the response and of the constraints are derived. These intermediate results are the basis for any subsequent second order study of the model. Despite the large number of parameters involved, bias formulae turn out to be quite simple due to the orthogonal structure of the model. In particular, the response estimators are shown to be approximately unbiased. Some simulations assess the validity of the approximations. 相似文献
7.
In this paper, we analyze the convergence of a projected fixed‐point iteration on a Riemannian manifold of matrices with fixed rank. As a retraction method, we use the projector splitting scheme. We prove that the convergence rate of the projector splitting scheme is bounded by the convergence rate of standard fixed‐point iteration without rank constraints multiplied by the function of initial approximation. We also provide counterexample to the case when conditions of the theorem do not hold. Finally, we support our theoretical results with numerical experiments. 相似文献
8.
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. 相似文献
9.
《Mathematical Methods in the Applied Sciences》2018,41(5):2074-2094
In this paper, we are mainly concerned with 2 types of constrained matrix equation problems of the form AXB=C, the least squares problem and the optimal approximation problem, and we consider several constraint matrices, such as general Toeplitz matrices, upper triangular Toeplitz matrices, lower triangular Toeplitz matrices, symmetric Toeplitz matrices, and Hankel matrices. In the first problem, owing to the special structure of the constraint matrix , we construct special algorithms; necessary and sufficient conditions are obtained about the existence and uniqueness for the solutions. In the second problem, we use von Neumann alternating projection algorithm to obtain the solutions of problem. Then we give 2 numerical examples to demonstrate the effectiveness of the algorithms. 相似文献
10.
Yongge Tian 《Numerical Linear Algebra with Applications》2013,20(5):713-722
A Hermitian matrix X is called a least‐squares solution of the inconsistent matrix equation AXA* = B, where B is Hermitian. A* denotes the conjugate transpose of A if it minimizes the F‐norm of B ? AXA*; it is called a least‐rank solution of AXA* = B if it minimizes the rank of B ? AXA*. In this paper, we study these two types of solutions by using generalized inverses of matrices and some matrix decompositions. In particular, we derive necessary and sufficient conditions for the two types of solutions to coincide. Copyright © 2012 John Wiley & Sons, Ltd. 相似文献
11.
数据拟合函数的加权最小二乘积分法 总被引:1,自引:0,他引:1
程毛林 《数学的实践与认识》2012,42(4):70-76
数据拟合的方法很多,每种方法各有特点.探讨了积分准则下的数据加权拟合函数的方法,称为加权最小二乘积分法,并给出了三个常用拟合函数具体形式. 相似文献
12.
In [6], an adaptive method to approximate unorganized clouds of points by smooth surfaces based on wavelets has been described. The general fitting algorithm operates on a coarse-to-fine basis. It selects on each refinement level in a first step a reduced number of wavelets which are appropriate to represent the features of the data set. In a second step, the fitting surface is constructed as the linear combination of the wavelets which minimizes the distance to the data in a least squares sense. This is followed by a thresholding procedure on the wavelet coefficients to discard those which are too small to contribute much to the surface representation.
In this paper, we firstly generalize this strategy to a classically regularized least squares functional by adding a Sobolev norm, taking advantage of the capability of wavelets to characterize Sobolev spaces of even fractional order. After recalling the usual cross-validation technique to determine the involved smoothing parameters, some examples of fitting severely irregularly distributed data, synthetically produced and of geophysical origin, are presented. In order to reduce computational costs, we then introduce a multilevel generalized cross-validation technique which goes beyond the Sobolev formulation and exploits the hierarchical setting based on wavelets. We illustrate the performance of the new strategy on some geophysical data.
AMS subject classification 65T60, 62G09, 93E14, 93E24We gratefully acknowledge the support by the Deutsche Forschungsgemeinschaft (KU 1028/7 1 and SFB 611) and by the Basque Government. 相似文献
13.
An n × n real matrix A = (aij)n × n is called bi‐symmetric matrix if A is both symmetric and per‐symmetric, that is, aij = aji and aij = an+1?1,n+1?i (i, j = 1, 2,..., n). This paper is mainly concerned with finding the least‐squares bi‐symmetric solutions of matrix inverse problem AX = B with a submatrix constraint, where X and B are given matrices of suitable sizes. Moreover, in the corresponding solution set, the analytical expression of the optimal approximation solution to a given matrix A* is derived. A direct method for finding the optimal approximation solution is described in detail, and three numerical examples are provided to show the validity of our algorithm. Copyright © 2007 John Wiley & Sons, Ltd. 相似文献
14.
Riccardo Fazio Alessandra Jannelli 《Mathematical Methods in the Applied Sciences》2017,40(18):6285-6294
As far as the numerical solution of boundary value problems defined on an infinite interval is concerned, in this paper, we present a test problem for which the exact solution is known. Then we study an a posteriori estimator for the global error of a nonstandard finite difference scheme previously introduced by the authors. In particular, we show how Richardson extrapolation can be used to improve the numerical solution using the order of accuracy and numerical solutions from 2 nested quasi‐uniform grids. We observe that if the grids are sufficiently fine, the Richardson error estimate gives an upper bound of the global error. 相似文献
15.
Rolf Krause Benjamin Müller Gerhard Starke 《Numerical Methods for Partial Differential Equations》2017,33(1):276-289
We present and analyze a least squares formulation for contact problems in linear elasticity which employs both, displacements and stresses, as independent variables. As a consequence, we obtain stability and high accuracy of our discretization also in the incompressible limit. Moreover, our formulation gives rise to a reliable and efficient a posteriori error estimator. To incorporate the contact constraints, the first‐order system least squares functional is augmented by a contact boundary functional which implements the associated complementarity condition. The bilinear form related to the augmented functional is shown to be coercive and therefore constitutes an upper bound, up to a constant, for the error in displacements and stresses in . This implies the reliability of the functional to be used as an a posteriori error estimator in an adaptive framework. The efficiency of the use of the functional as an a posteriori error estimator is monitored by the local proportion of the boundary functional term with respect to the overall functional. Computational results using standard conforming linear finite elements for the displacement approximation combined with lowest‐order Raviart‐Thomas elements for the stress tensor show the effectiveness of our approach in an adaptive framework for two‐dimensional and three‐dimensional Hertzian contact problems. © 2016 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 276–289, 2017 相似文献
16.
Bilinear tensor least squares problems occur in applications such as Hammerstein system identification and social network analysis. A linearly constrained problem of medium size is considered, and nonlinear least squares solvers of Gauss–Newton‐type are applied to numerically solve it. The problem is separable, and the variable projection method can be used. Perturbation theory is presented and used to motivate the choice of constraint. Numerical experiments with Hammerstein models and random tensors are performed, comparing the different methods and showing that a variable projection method performs best. 相似文献
17.
Tadashi Nakamura Chae-Shin Lee 《Annals of the Institute of Statistical Mathematics》1993,45(4):741-758
When random samples are drawn from a 3-parameter distribution with a shifted origin and the observations corresponding to each sample are binary, criteria for the existence of minimum contrast estimates are given. These criteria can be drived by a method, called the probability contents boundary analysis. The probabilities of the existence of maximum likelihood estimates and least squares estimates are evaluated, by simulation with 1000 replications, in the case where the underlying distribution is a 3-parameter lognormal distribution or a 3-parameter loglogistic distribution. 相似文献