ترغب بنشر مسار تعليمي؟ اضغط هنا

The Epsilon-Alternating Least Squares for Orthogonal Low-Rank Tensor Approximation and Its Global Convergence

82   0   0.0 ( 0 )
 نشر من قبل Yuning Yang
 تاريخ النشر 2019
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English
 تأليف Yuning Yang




اسأل ChatGPT حول البحث

The epsilon alternating least squares ($epsilon$-ALS) is developed and analyzed for canonical polyadic decomposition (approximation) of a higher-order tensor where one or more of the factor matrices are assumed to be columnwisely orthonormal. It is shown that the algorithm globally converges to a KKT point for all tensors without any assumption. For the original ALS, by further studying the properties of the polar decomposition, we also establish its global convergence under a reality assumption not stronger than those in the literature. These results completely address a question concerning the global convergence raised in [L. Wang, M. T. Chu and B. Yu, emph{SIAM J. Matrix Anal. Appl.}, 36 (2015), pp. 1--19]. In addition, an initialization procedure is proposed, which possesses a provable lower bound when the number of columnwisely orthonormal factors is one. Armed with this initialization procedure, numerical experiments show that the $epsilon$-ALS exhibits a promising performance in terms of efficiency and effectiveness.



قيم البحث

اقرأ أيضاً

96 - Yuning Yang 2020
The goal of this work is to fill a gap in [Yang, SIAM J. Matrix Anal. Appl, 41 (2020), 1797--1825]. In that work, an approximation procedure was proposed for orthogonal low-rank tensor approximation; however, the approximation lower bound was only es tablished when the number of orthonormal factors is one. To this end, by further exploring the multilinearity and orthogonality of the problem, we introduce a modified approximation algorithm. Approximation lower bound is established, either in deterministic or expected sense, no matter how many orthonormal factors there are. In addition, a major feature of the new algorithm is its flexibility to allow either deterministic or randomized procedures to solve a key step of each latent orthonormal factor involved in the algorithm. This feature can reduce the computation of large SVDs, making the algorithm more efficient. Some numerical studies are provided to validate the usefulness of the proposed algorithm.
In this work, we study the tensor ring decomposition and its associated numerical algorithms. We establish a sharp transition of algorithmic difficulty of the optimization problem as the bond dimension increases: On one hand, we show the existence of spurious local minima for the optimization landscape even when the tensor ring format is much over-parameterized, i.e., with bond dimension much larger than that of the true target tensor. On the other hand, when the bond dimension is further increased, we establish one-loop convergence for alternating least square algorithm for tensor ring decomposition. The theoretical results are complemented by numerical experiments for both local minimum and one-loop convergence for the alternating least square algorithm.
The null distributed controllability of the semilinear heat equation $y_t-Delta y + g(y)=f ,1_{omega}$, assuming that $g$ satisfies the growth condition $g(s)/(vert svert log^{3/2}(1+vert svert))rightarrow 0$ as $vert svert rightarrow infty$ and that $g^primein L^infty_{loc}(mathbb{R})$ has been obtained by Fernandez-Cara and Zuazua in 2000. The proof based on a fixed point argument makes use of precise estimates of the observability constant for a linearized heat equation. It does not provide however an explicit construction of a null control. Assuming that $g^primein W^{s,infty}(mathbb{R})$ for one $sin (0,1]$, we construct an explicit sequence converging strongly to a null control for the solution of the semilinear equation. The method, based on a least-squares approach, generalizes Newton type methods and guarantees the convergence whatever be the initial element of the sequence. In particular, after a finite number of iterations, the convergence is super linear with a rate equal to $1+s$. Numerical experiments in the one dimensional setting support our analysis.
The alternating least squares algorithm for CP and Tucker decomposition is dominated in cost by the tensor contractions necessary to set up the quadratic optimization subproblems. We introduce a novel family of algorithms that uses perturbative corre ctions to the subproblems rather than recomputing the tensor contractions. This approximation is accurate when the factor matrices are changing little across iterations, which occurs when alternating least squares approaches convergence. We provide a theoretical analysis to bound the approximation error. Our numerical experiments demonstrate that the proposed pairwise perturbation algorithms are easy to control and converge to minima that are as good as alternating least squares. The experimental results show improvements of up to 3.1X with respect to state-of-the-art alternating least squares approaches for various model tensor problems and real datasets.
We introduce and analyze a space-time least-squares method associated to the unsteady Navier-Stokes system. Weak solution in the two dimensional case and regular solution in the three dimensional case are considered. From any initial guess, we constr uct a minimizing sequence for the least-squares functional which converges strongly to a solution of the Navier-Stokes system. After a finite number of iterates related to the value of the viscosity constant, the convergence is quadratic. Numerical experiments within the two dimensional case support our analysis. This globally convergent least-squares approach is related to the damped Newton method when used to solve the Navier-Stokes system through a variational formulation.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا