Simultaneous state‐time approximation of the chemical master equation using tensor product formats

We apply the novel tensor product formats (tensor train, quantized TT [QTT], and QTT‐Tucker) to the solution of d‐dimensional chemical master equations for gene regulating networks (signaling cascades, toggle switches, and phage‐ λ). For some important cases, for example, signaling cascade models, we prove analytical tensor product representations of the system operator. The quantized tensor representations (QTT, QTT‐Tucker) are employed in both state space and time, and the global state‐time (d + 1)‐dimensional system is solved in the tensor product form by the alternating minimal energy iteration, the ALS‐type algorithm. This approach leads to the logarithmic dependence of the computational complexity on the volume of the state space. We investigate the proposed technique numerically and compare it with the direct chemical master equation solution and some previously known approximate schemes, where possible. We observe that the newer tensor methods demonstrate a good potential in simulation of relevant biological systems. Copyright © 2014 John Wiley & Sons, Ltd.     

Fast tensor method for summation of long‐range potentials on 3D lattices with defects

In this paper, we present a method for fast summation of long‐range potentials on 3D lattices with multiple defects and having non‐rectangular geometries, based on rank‐structured tensor representations. This is a significant generalization of our recent technique for the grid‐based summation of electrostatic potentials on the rectangular L × L × L lattices by using the canonical tensor decompositions and yielding the O(L) computational complexity instead of O(L³) by traditional approaches. The resulting lattice sum is calculated as a Tucker or canonical representation whose directional vectors are assembled by the 1D summation of the generating vectors for the shifted reference tensor, once precomputed on large N × N × N representation grid in a 3D bounding box. The tensor numerical treatment of defects is performed in an algebraic way by simple summation of tensors in the canonical or Tucker formats. To diminish the considerable increase in the tensor rank of the resulting potential sum, the ?‐rank reduction procedure is applied based on the generalized reduced higher‐order SVD scheme. For the reduced higher‐order SVD approximation to a sum of canonical/Tucker tensors, we prove the stable error bounds in the relative norm in terms of discarded singular values of the side matrices. The required storage scales linearly in the 1D grid‐size, O(N), while the numerical cost is estimated by O(NL). The approach applies to a general class of kernel functions including those for the Newton, Slater, Yukawa, Lennard‐Jones, and dipole‐dipole interactions. Numerical tests confirm the efficiency of the presented tensor summation method; we demonstrate that a sum of millions of Newton kernels on a 3D lattice with defects/impurities can be computed in seconds in Matlab implementation. The tensor approach is advantageous in further functional calculus with the lattice potential sums represented on a 3D grid, like integration or differentiation, using tensor arithmetics of 1D complexity. Copyright © 2015 John Wiley & Sons, Ltd.     

O(dlog?N)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling

In the present paper, we discuss the novel concept of super-compressed tensor-structured data formats in high-dimensional applications. We describe the multifolding or quantics-based tensor approximation method of O(dlog N)-complexity (logarithmic scaling in the volume size), applied to the discrete functions over the product index set {1,…,N}^⊗d , or briefly N-d tensors of size N ^d , and to the respective discretized differential-integral operators in ℝ ^d . As the basic approximation result, we prove that a complex exponential sampled on an equispaced grid has quantics rank 1. Moreover, a Chebyshev polynomial, sampled over a Chebyshev Gauss–Lobatto grid, has separation rank 2 in the quantics tensor format, while for the polynomial of degree m over a Chebyshev grid the respective quantics rank is at most 2m+1. For N-d tensors generated by certain analytic functions, we give a constructive proof of the O(dlog Nlog ε ⁻¹)-complexity bound for their approximation by low-rank 2-(dlog N) quantics tensors up to the accuracy ε>0. In the case ε=O(N ^−α ), α>0, our approach leads to the quantics tensor numerical method in dimension d, with the nearly optimal asymptotic complexity O(d/αlog ² ε ⁻¹). From numerical examples presented here, we observe that the quantics tensor method has proved its value in application to various function related tensors/matrices arising in computational quantum chemistry and in the traditional finite element method/boundary element method (FEM/BEM). The tool apparently works.     

Subtracting a best rank‐1 approximation from p × p × 2(p≥2) tensors

We introduce one special form of the ptimesp × 2 (p≥2) tensors by multilinear orthonormal transformations, and present some interesting properties of the special form. Through discussing on the special form, we provide a solution to one conjecture proposed by Stegeman and Comon in a conference paper (Proceedings of the EUSIPCO 2009 Conference, Glasgow, Scotland, 2009), and reveal an important conclusion about subtracting a best rank‐1 approximations from p × p × 2 tensors of the special form. All of these confirm that consecutively subtracting the best rank‐1 approximations may not lead to a best low rank approximation of a tensor. Numerical examples show the correctness of our theory. Copyright © 2011 John Wiley & Sons, Ltd.     

News Algorithms for tensor decomposition based on a reduced functional

We study the least squares functional of the canonical polyadic tensor decomposition for third order tensors by eliminating one factor matrix, which leads to a reduced functional. An analysis of the reduced functional leads to several equivalent optimization problem, such as a Rayleigh quotient or a projection. These formulations are the basis of several new algorithms as follows: the Centroid Projection method for efficient computation of suboptimal solutions and fixed‐point iteration methods for approximating the best rank‐1 and the best rank‐R decompositions under certain nondegeneracy conditions. Copyright © 2013 John Wiley & Sons, Ltd.     

A nonlinearly preconditioned conjugate gradient algorithm for rank‐R canonical tensor approximation

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.     

Low rank Tucker-type tensor approximation to classical potentials

This paper investigates best rank-(r ₁,..., r _d ) Tucker tensor approximation of higher-order tensors arising from the discretization of linear operators and functions in ℝ ^d . Super-convergence of the best rank-(r ₁,..., r _d ) Tucker-type decomposition with respect to the relative Frobenius norm is proven. Dimensionality reduction by the two-level Tucker-to-canonical approximation is discussed. Tensor-product representation of basic multi-linear algebra operations is considered, including inner, outer and Hadamard products. Furthermore, we focus on fast convolution of higher-order tensors represented by the Tucker/canonical models. Optimized versions of the orthogonal alternating least-squares (ALS) algorithm is presented taking into account the different formats of input data. We propose and test numerically the mixed CT-model, which is based on the additive splitting of a tensor as a sum of canonical and Tucker-type representations. It allows to stabilize the ALS iteration in the case of “ill-conditioned” tensors. The best rank-(r ₁,..., r _d ) Tucker decomposition is applied to 3D tensors generated by classical potentials, for example and with x, y ∈ ℝ ^d . Numerical results for tri-linear decompositions illustrate exponential convergence in the Tucker rank, and robustness of the orthogonal ALS iteration.      

Low‐rank approximation of tensors via sparse optimization

The goal of this paper is to find a low‐rank approximation for a given nth tensor. Specifically, we give a computable strategy on calculating the rank of a given tensor, based on approximating the solution to an NP‐hard problem. In this paper, we formulate a sparse optimization problem via an l₁‐regularization to find a low‐rank approximation of tensors. To solve this sparse optimization problem, we propose a rescaling algorithm of the proximal alternating minimization and study the theoretical convergence of this algorithm. Furthermore, we discuss the probabilistic consistency of the sparsity result and suggest a way to choose the regularization parameter for practical computation. In the simulation experiments, the performance of our algorithm supports that our method provides an efficient estimate on the number of rank‐one tensor components in a given tensor. Moreover, this algorithm is also applied to surveillance videos for low‐rank approximation.     

Spectral Algorithms for Tensor Completion

In the tensor completion problem, one seeks to estimate a low‐rank tensor based on a random sample of revealed entries. In terms of the required sample size, earlier work revealed a large gap between estimation with unbounded computational resources (using, for instance, tensor nuclear norm minimization) and polynomial‐time algorithms. Among the latter, the best statistical guarantees have been proved, for third‐order tensors, using the sixth level of the sum‐of‐squares (sos ) semidefinite programming hierarchy. However, the sos approach does not scale well to large problem instances. By contrast, spectral methods—based on unfolding or matricizing the tensor—are attractive for their low complexity, but have been believed to require a much larger sample size. This paper presents two main contributions. First, we propose a new method, based on unfolding, which outperforms naive ones for symmetric k^th‐order tensors of rank r. For this result we make a study of singular space estimation for partially revealed matrices of large aspect ratio, which may be of independent interest. For third‐order tensors, our algorithm matches the sos method in terms of sample size (requiring about rd^3/2 revealed entries), subject to a worse rank condition (r ≪ d^3/4 rather than r ≪ d^3/2). We complement this result with a different spectral algorithm for third‐order tensors in the overcomplete (r ≥ d) regime. Under a random model, this second approach succeeds in estimating tensors of rank d ≤ r ≪ d^3/2 from about rd^3/2 revealed entries. © 2018 Wiley Periodicals, Inc.     

Cross approximation in tensor electron density computations

We propose new tensor approximation algorithms for certain discrete functions related with Hartree–Fock/Kohn–Sham equations. Given a canonical tensor representation for the electron density function (for example, produced by quantum chemistry packages such as MOLPRO), we obtain its Tucker approximation with much fewer parameters than the input data and the Tucker approximation for the cubic root of this function, which is part of the Kohn–Sham exchange operator. The key idea is in the fast and accurate prefiltering of possibly large‐scale factors of the canonical tensor input. The new algorithms are based on the incomplete cross approximation method applied to matrices and tensors of order 3 and outperform other tools for the same purpose. First, we show that the cross approximation method is robust and much faster than the singular value decomposition‐based approach. As a consequence, it becomes possible to increase the resolution of grid and the complexity of molecules that can be handled by the Hartree–Fock chemical models. Second, we propose a new fast approximation method for f^1/3(x, y, z), based on the factor prefiltering method for f(x, y, z) and certain mimic approximation hypothesis. Third, we conclude that the Tucker format has advantages in the storage and computation time compared with the ubiquitous canonical format. Copyright © 2009 John Wiley & Sons, Ltd.     

Dirac particle in generalized Pöschl–Teller field including a Coulomb‐like tensor coupling: super‐symmetric solution

In the presence of pseudo‐spin (p‐spin) and spin symmetries, we use the super‐symmetric formalism to solve the Dirac equation with the generalized Pöschl–Teller potential including the Coulomb‐like tensor interaction with any arbitrary spin‐orbit quantum number κ.. Using the Greene–Aldrich usual approximation scheme to deal with pseudo‐centrifugal or centrifugal rotational kinetic energy l (l + 1) ∕ r² or , we obtain the Pseudo‐spin and spin‐symmetric energy eigenvalue equation and the normalized upper and lower components of the radial wave functions in closed form. The presence of the tensor coupling interaction removes the degeneracy in the p‐spin and spin doublets. Copyright © 2013 John Wiley & Sons, Ltd.     

Best N Term Approximation Spaces for Tensor Product Wavelet Bases

We consider best N term approximation using anisotropic tensor product wavelet bases ("sparse grids"). We introduce a tensor product structure ⊗_q on certain quasi-Banach spaces. We prove that the approximation spaces A^α_q(L₂) and A^α_q(H¹) equal tensor products of Besov spaces B^α_q(L_q), e.g., A^α_q(L₂([0,1]^d)) = B^α_q(L_q([0,1])) ⊗_q · ⊗_q B^α_{q · ·}(L_q([0,1])). Solutions to elliptic partial differential equations on polygonal/polyhedral domains belong to these new scales of Besov spaces.     

The quadratic plus the tensor potentials for particle with 1/2‐spin via L2 method under the spin symmetry

In the present letter, the relativistic equation for particle 1/2‐spin have been obtained for the quadratic scalar and vector potentials in the presence of the tensor interaction that depends on the radial component either linearly and inversely. Under the spin symmetry, the relativistic equation is calculated by using the idea of L² that supports a tridiagonal matrix representation of the wave operator. By this requirement, the relativistic energy spectrum and corresponding spinor wave functions are obtained. Also, the obtained analytically result is compared with other results that are in good agreement. Some of the numerical results are given, too. Copyright © 2015 John Wiley & Sons, Ltd.     

Raising approximation order of refinable vector by increasing multiplicity

An algorithm is presented for raising an approximation order of any given orthogonal multiscaling function with the dilation factor a. Let φ(x) = [φ1(x),φ2(x),…,φr(x)]T be an orthogonal multiscaling function with the dilation factor a and the approximation order m. We can construct a new orthogonal multiscaling function φnew(x) = [ φT(x). f3r 1(x),φr 2(x),…,φr s(x)}T with the approximation order m L(L ∈ Z ). In other words, we raise the approximation order of multiscaling function φ(x) by increasing its multiplicity. In addition, we discuss an especial setting. That is, if given an orthogonal multiscaling function φ(x) = [φ1 (x), φ2(x), …, φr(x)]T is symmetric, then the new orthogonal multiscaling function φnew(x) not only raise the approximation order but also preserve symmetry. Finally, some examples are given.     

Best rank one approximation of real symmetric tensors can be chosen symmetric

We show that a best rank one approximation to a real symmetric tensor, which in principle can be nonsymmetric, can be chosen symmetric. Furthermore, a symmetric best rank one approximation to a symmetric tensor is unique if the tensor does not lie on a certain real algebraic variety.     

On the approximation power of bivariate splines

We show how to construct stable quasi-interpolation schemes in the bivariate spline spaces S _d ^r (Δ) with d⩾ 3r + 2 which achieve optimal approximation order. In addition to treating the usual max norm, we also give results in the L _p norms, and show that the methods also approximate derivatives to optimal order. We pay special attention to the approximation constants, and show that they depend only on the smallest angle in the underlying triangulation and the nature of the boundary of the domain. This revised version was published online in August 2006 with corrections to the Cover Date.     

完备流形上拉普拉斯算子的L2特征形式

本文研究了完备非紧流行上拉普拉斯算子的L²特征形式.利用应力能量张量的方法,得到在此类流形上拉普拉斯算子的L²特征形式的一些不存在性定理。     

Functional Quantization and Small Ball Probabilities for Gaussian Processes

Quantization consists in studying the L ^r -error induced by the approximation of a random vector X by a vector (quantized version) taking a finite number n of values. We investigate this problem for Gaussian random vectors in an infinite dimensional Banach space and in particular, for Gaussian processes. A precise link proved by Fehringer⁽⁴⁾ and Dereich et al. ⁽³⁾ relates lower and upper bounds for small ball probabilities with upper and lower bounds for the quantization error, respectively. We establish a complete relationship by showing that the same holds for the direction from the quantization error to small ball probabilities. This allows us to compute the exact rate of convergence to zero of the minimal L ^r -quantization error from logarithmic small ball asymptotics and vice versa.     

Approximation of functions by certain nonlinear integral operators

We study approximation properties of certain nonlinear integral operators L _n * obtained by a modification of given operators L _n . The operators L _n;r and L _n;r * of r-times differentiable functions are also studied. We give theorems on approximation orders of functions by these operators in polynomial weight spaces.     

On the tensor square of non-abelian nilpotent finite-dimensional Lie algebras

For every finite p-group G of order p ⁿ with derived subgroup of order p ^m , Rocco [N.R. Rocco, On a construction related to the nonabelian tensor square of a group, Bol. Soc. Brasil. Mat. 1 (1991), pp. 63–79] proved that the order of tensor square of G is at most p ^n(n?m). This upper bound has been improved recently by the author [P. Niroomand, On the order of tensor square of non abelian prime power groups (submitted)]. The aim of this article is to obtain a similar result for a non-abelian nilpotent Lie algebra of finite dimension. More precisely, for any given n-dimensional non-abelian nilpotent Lie algebra L with derived subalgebra of dimension m we have dim(L???L)?≤?(n???m)(n???1)?+?2. Furthermore for m?=?1, the explicit structure of L is given when the equality holds.