Subtracting a best rank-1 approximation may increase tensor rank

It has been shown that a best rank-R approximation of an order-k tensor may not exist when R?2 and k?3. This poses a serious problem to data analysts using tensor decompositions. It has been observed numerically that, generally, this issue cannot be solved by consecutively computing and subtracting best rank-1 approximations. The reason for this is that subtracting a best rank-1 approximation generally does not decrease tensor rank. In this paper, we provide a mathematical treatment of this property for real-valued 2×2×2 tensors, with symmetric tensors as a special case. Regardless of the symmetry, we show that for generic 2×2×2 tensors (which have rank 2 or 3), subtracting a best rank-1 approximation results in a tensor that has rank 3 and lies on the boundary between the rank-2 and rank-3 sets. Hence, for a typical tensor of rank 2, subtracting a best rank-1 approximation increases the tensor rank.     

A new type of C -numerical range arising in quantum computing

We consider a new type of numerical range motivated by recent applications in quantum computing. We term the object of interest local C -numerical rangeW_loc(C, A) of A. It is obtained by replacing the special unitary group in the definition of the C -numerical range by the so-called local subgroup of SU (2^N ), i.e. by the N -fold tensor product SU (2) ⊗ · · · ⊗ SU(2) of unitary (2 × 2)-matrices. First, it is shown that the local C -numerical range has rather unusual geometric properties compared to the ordinary one, e.g. it is in general neither star-shaped nor simply connected. Then two numerical algorithms, a Newton and a conjugate gradient method on the Lie group SU (2) ⊗ · · · ⊗ SU (2), are demonstrated to maximize the real part of W_loc(C, A) which also gives a Euclidean measure of the so-called pure-state entanglement in quantum computing. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.      

Moduli of symplectic instanton vector bundles of higher rank on projective space ℙ<Superscript>3</Superscript>

Symplectic instanton vector bundles on the projective space ℙ³ constitute a natural generalization of mathematical instantons of rank-2. We study the moduli space I _n;r of rank-2r symplectic instanton vector bundles on ℙ³ with r ≥ 2 and second Chern class n ≥ r, n ≡ r (mod 2). We introduce the notion of tame symplectic instantons by excluding a kind of pathological monads and show that the locus I _n;r ^* of tame symplectic instantons is irreducible and has the expected dimension, equal to 4n(r + 1) −r(2r + 1).     

Quantized CP approximation and sparse tensor interpolation of function‐generated data

In this article, we consider the iterative schemes to compute the canonical polyadic (CP) approximation of quantized data generated by a function discretized on a large uniform grid in an interval on the real line. This paper continues the research on the quantics‐tensor train (QTT) method (“O(d log N)‐quantics approximation of N‐d tensors in high‐dimensional numerical modeling” in Constructive Approximation, 2011) developed for the tensor train (TT) approximation of the quantized images of function related data. In the QTT approach, the target vector of length 2^L is reshaped to a Lth‐order tensor with two entries in each mode (quantized representation) and then approximated by the QTT tensor including 2r²L parameters, where r is the maximal TT rank. In what follows, we consider the alternating least squares (ALS) iterative scheme to compute the rank‐r CP approximation of the quantized vectors, which requires only 2rL?2^L parameters for storage. In the earlier papers (“Tensors‐structured numerical methods in scientific computing: survey on recent advances” in Chemom Intell Lab Syst, 2012), such a representation was called Q_Can format, whereas in this paper, we abbreviate it as the QCP (quantized canonical polyadic) representation. We test the ALS algorithm to calculate the QCP approximation on various functions, and in all cases, we observed the exponential error decay in the QCP rank. The main idea for recovering a discretized function in the rank‐r QCP format using the reduced number of the functional samples, calculated only at O(2rL) grid points, is presented. The special version of the ALS scheme for solving the arising minimization problem is described. This approach can be viewed as the sparse QCP‐interpolation method that allows to recover all 2rL representation parameters of the rank‐r QCP tensor. Numerical examples show the efficiency of the QCP‐ALS‐type iteration and indicate the exponential convergence rate in r.     

The rank of a 2 × 2 × 2 tensor

As computing power increases, many more problems in engineering and data analysis involve computation with tensors, or multi-way data arrays. Most applications involve computing a decomposition of a tensor into a linear combination of rank-1 tensors. Ideally, the decomposition involves a minimal number of terms, i.e. computation of the rank of the tensor. Tensor rank is not a straight-forward extension of matrix rank. A constructive proof based on an eigenvalue criterion is provided that shows when a 2?×?2?×?2 tensor over ? is rank-3 and when it is rank-2. The results are extended to show that n?×?n?×?2 tensors over ? have maximum possible rank n?+?k where k is the number of complex conjugate eigenvalue pairs of the matrices forming the two faces of the tensor cube.     

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.     

A note on semidefinite programming relaxations for polynomial optimization over a single sphere

We study two instances of polynomial optimization problem over a single sphere. The first problem is to compute the best rank-1 tensor approximation. We show the equivalence between two recent semidefinite relaxations methods. The other one arises from Bose-Einstein condensates (BEC), whose objective function is a summation of a probably nonconvex quadratic function and a quartic term. These two polynomial optimization problems are closely connected since the BEC problem can be viewed as a structured fourth-order best rank-1 tensor approximation. We show that the BEC problem is NP-hard and propose a semidefinite relaxation with both deterministic and randomized rounding procedures. Explicit approximation ratios for these rounding procedures are presented. The performance of these semidefinite relaxations are illustrated on a few preliminary numerical experiments.     

Structured multi-way arrays and their applications

Based on the structure of the rank-1 matrix and the different unfolding ways of the tensor, we present two types of structured tensors which contain the rank-1 tensors as special cases. We study some properties of the ranks and the best rank-r approximations of the structured tensors. By using the upper-semicontinuity of the matrix rank, we show that for the structured tensors, there always exist the best rank-r approximations. This can help one to better understand the sequential unfolding singular value decomposition (SVD) method for tensors proposed by J. Salmi et al. [IEEE Trans Signal Process, 2009, 57(12): 4719–4733] and offer a generalized way of low rank approximations of tensors. Moreover, we apply the structured tensors to estimate the upper and lower bounds of the best rank-1 approximations of the 3rd-order and 4th-order tensors, and to distinguish the well written and non-well written digits.     

Directional approximation of the jacobians in ROW-methods

In this paper a new technique for avoiding exact Jacobians in ROW methods is proposed. The Jacobiansf' _n are substituted by matricesA _n satisfying a directional consistency conditionA _n f _n =f' _n f _n +O(h). In contrast to generalW-methods this enables us to reduce the number of order conditions and we construct a 2-stage method of order 3 and families of imbedded 4-stage methods of order 4(3). The directional approximation of the Jacobians has been realized via rank-1 updating as known from quasi-Newton methods.     

Asymptotic Behaviour of Best lp-Approximations from Affi ne Subspaces

In this paper we consider the problem of best approximation in ℓ_pⁿ, 1<p∞. If h_p, 1<p<∞, denotes the best ℓ_p-approximation of the element h ⁿ from a proper affine subspace K of ⁿ, hK, then lim_p→∞h_p=h_∞^*, where h_∞^* is a best uniform approximation of h from K, the so-called strict uniform approximation. Our aim is to prove that for all r there are α_j ⁿ, 1jr, such that

Full-size image

, with γ_p^{(r) n} and γ_p^(r)= (p^−r−1).     

Infinite products for power series

An algorithm is introduced and shown to lead to a unique infinite product representation for a given formal power series A(z) with A(0) = 1. The infinite product is , where all b_n ≠ 0, r_n , and r_n+1 > r_n. The degree of approximation by the polynomial (1 + b₁z^r₁) · · · (1 + b_nz^r_n) is also considered.     

On the Degeneracy Locus of a Map of Vector Bundles on Grassamannian Varieties

Let ℒ︁ be a line bundle on a smooth curve C of genus g ≥ 2 and let W ⊂ H⁰ (ℒ︁) be a subspace of dimension r +1, in this paper we study the natural map μ_W : W ⊗ H⁰ (ω_C) → H⁰ (ℒ︁ ⊗ ω_C). Let D ⊂ G(r + 1, H⁰(ℒ︁)) be the locus where μ_W fails to be surjective: we prove that, if C is not hyperelliptic of genus g ≥ 3, D is an irreducible and reduced divisor on G(r + 1, H⁰(ℒ︁)) for any r ≥ 3, and for r = 2 if the curve C is not trigonal.     

Bernstein-Durrmeyer算子拟中插式在Orlicz空间中的逼近

本文在Orlicz空间中研究了Bernstein-Durrmeyer算子拟中插式B_n~(2r-1)(f,x)逼近性质.利用2r阶Ditzian-Totik模与K-泛函的等价性,Jensen不等式,H?lder不等式,Berens-Lorentz引理得到了逼近的正,逆和等价定理,从而推广了Bernstein-Durrmeyer算子拟中插式B_n~(2r-1)(f,x)在L_P空间的逼近结果.     

ON THE ORDER OF APPROXIMATION FOR THE RATIONAL INTERPOLATION TO ｜x｜

The order of approximation for Newman-type rational interpolation to |x| is studied in this paper. For general set of nodes, the extremum of approximation error and the order of the best uniform approximation are estimated. The result illustrates the general quality of approximation in a different way. For the special case where the interpolation nodes are $x_i = \left( {\frac{i}{n}} \right)^r (i = 1,2, \cdots ,n;r > 0)$x_i = \left( {\frac{i}{n}} \right)^r (i = 1,2, \cdots ,n;r > 0) , it is proved that the exact order of approximation is O( \frac1n ),O( \frac1nlogn ) and O( \frac1n^r )O\left( {\frac{1}{n}} \right),O\left( {\frac{1}{{n\log n}}} \right) and O\left( {\frac{1}{{n^r }}} \right) , respectively, corresponding to 01.     

Maximally mobile Davies metric spaces

The spaces whose linear elements are given by a homogeneous function of degree two with respect to the direction arguments are studied. The maximal order of the group of motionsG _r (r=n(n–1)/2+2) in Davies spaces is determined. A tensor characterization of maximally mobile spaces is given.Translated from Ukrainskií Geometricheskií Sbornik, Issue 29, 1986, pp. 47–54.     

Complexity of Weighted Approximation over

We study approximation of univariate functions defined over the reals. We assume that the rth derivative of a function is bounded in a weighted L_p norm with a weight ψ. Approximation algorithms use the values of a function and its derivatives up to order r−1. The worst case error of an algorithm is defined in a weighted L_q norm with a weight ρ. We study the worst case (information) complexity of the weighted approximation problem, which is equal to the minimal number of function and derivative evaluations needed to obtain error . We provide necessary and sufficient conditions in terms of the weights ψ and ρ, as well as the parameters r, p, and q for the weighted approximation problem to have finite complexity. We also provide conditions which guarantee that the complexity of weighted approximation is of the same order as the complexity of the classical approximation problem over a finite interval. Such necessary and sufficient conditions are also provided for a weighted integration problem since its complexity is equivalent to the complexity of the weighted approximation problem for q=1.     

On sparse reconstruction from Fourier and Gaussian measurements

This paper improves upon best‐known guarantees for exact reconstruction of a sparse signal f from a small universal sample of Fourier measurements. The method for reconstruction that has recently gained momentum in the sparse approximation theory is to relax this highly nonconvex problem to a convex problem and then solve it as a linear program. We show that there exists a set of frequencies Ω such that one can exactly reconstruct every r‐sparse signal f of length n from its frequencies in Ω, using the convex relaxation, and Ω has size A random set Ω satisfies this with high probability. This estimate is optimal within the log logn and log³r factors. We also give a relatively short argument for a similar problem with k(r, n) ≈ r[12 + 8 log(n/r)] Gaussian measurements. We use methods of geometric functional analysis and probability theory in Banach spaces, which makes our arguments quite short. © 2007 Wiley Periodicals, Inc.     

Fuzzy complex Grassmannians and quantization of line bundles

We construct by purely representation-theoretic methods fuzzy versions of an arbitrary complex Grassmannian M=Gr _n (ℂ ^n+m ), i.e., a sequence of matrix algebras tending SU(n+m)-equivariantly to the algebra of smooth functions on M. We also show that this approximation can be interpreted in terms of the Berezin-Toeplitz quantization of M. Furthermore, we use branching rules to prove that the quantization of every complex line bundle over M is given by a SU(n+m)-equivariant truncation of the space of its L ²-sections.