Xinhua Su,Ran Tao

Abstract:Tensor analysis approaches are of great importance in various fields such as computation vision and signal processing.Thereinto,the definitions of tensor-tensor product (t-product)and tensor singular value decomposition (t-SVD) are significant in practice.This work presents new t-product and t-SVD definitions based on the discrete simplified fractional Fourier transform(DSFRFT).The proposed definitions can effectively deal with special complex tenors,which further motivates the transform based tensor analysis approaches.Then,we define a new tensor nuclear norm induced by the DSFRFT based t-SVD.In addition,we analyze the computational complexity of the proposed t-SVD,which indicates that the proposed t-SVD can improve the computational efficiency.

Keywords:tensor-tensor product;tensor singular value decomposition;fractional Fourier transform

1 Introduction

With the advance in information science,the data are usually stored in multiway arrays called tensors,which can express more rich and comprehensive information.Tensor analysis is of great importance in various fields,including computation vision [1]and signal processing [2],etc.Since tensors are the generalization of matrices,it seems natural to transform tensors to matrices and apply the existing classical methods to solve the tensor problems.However,these methods can not take advantages of complex structure of tensors and cause the performance degradation.Several tensor factorization (TF) methods and definitions of tensor ranks have been proposed,but each of them has its shortcoming.The Candecomp/Parafac (CP) rank is defined as the minimum number of rank-one tensor decomposition.It is usually NP-hard to calculate and its convex envelop is unclear [3,4].The Tucker rank is a vector,whose element is matrix rank function of mode-i matricization of a tensor [5].The sum of the nuclear norm (SNN),as a convex relaxation of the Tucker rank,is widely applied.However,SNN is not the convex envelop of the Tucker rank,which achieves the suboptimal solution substantially [6].Recently,based on tensortensor product (t-product) and tensor singular value decomposition (t-SVD),the tensor nuclear norm (TNN),as the convex envelop of the tensor average rank,is defined in [7,8].TNNbased models are effective applied in tensor completion [9,10]and tensor robust principal component analysis (PCA) [8].Note that,based on the discrete Fourier transform (DFT),t-product can be regarded as the convolution-like operation.In addition,for a real tensor the conjugate symmetry of DFT leads to a more efficient method for computing t-product and t-SVD.In [11],the authors proposed a more general t-product and t-SVD based on different real linear transforms.Besides,similar to TNN,the transform based TNN is proposed,which is significant in dealing with different real tensors.

In practice,we also need to deal with various complex tensors [12,13].For example,for chirp complex tensors,chirp parameter estimation based on TF methods have been studied[14].In order to further improve the efficiency for computing t-product and t-SVD,we propose tproduct and t-SVD based on the discrete simplified fractional Fourier transform (DSFRFT).Then,a new tensor nuclear norm is defined based on the proposed t-SVD.These definitions further motivates the transform based tensor analysis approaches.In addition,as the concrete analysis in Section 3,the computation of DSFRFT based tproduct and t-SVD are more efficient than those based on DFT.The above definitions based on DSFRFT can reduce to the existing definitions based on DFT when DSFRFT reduces to DFT with the appropriate parameter.

2 TF Induced by DSFRFT

2.1 DSFRFT

The simplified fractional Fourier transform(SFRFT) ofx(t) is defined as follows

2.2 Tensor Nuclear Norm Induced by DSFRFT Based T-SVD

2.3 T-product and T-SVD

Definition 5(F-diagonal tensor[11]) A tensor is called f-diagonal if each of its frontal slices is a diagonal matrix.

Theorem 1(T-SVD) LetSbe the DSFRFT operator in (10) andA ∈Cn1×n2×n3 is a chirp tensor.Then it can be factorized as

Definition 6(Tensor tubal rank[11]) The tensor tubal rank,denoted as rankt(A),is defined as the number of nonzero singular tubes ofT,whereTis from the t-SVD ofA=U ?S T ?S V?,i.e.,

The tensor tubal rank is nonconvex.As the convex surrogate of rankt(A),the convex tensor nuclear norm can be defined inspired by the proof in [11].As the matrix case,the tensor nuclear norm is the dual norm of the tensor spectral norm.Thus,the definition of the tensor spectral norm is significant.

3 Computational Complexity

In this section,we compare the computation complexity of t-SVD based on DSFRFT in Algorithm 1 and t-SVD based on DFT for a chirp tensor.The proposed t-SVD includes three parts:the DSFRFT,SVD of the transformed matrices and the inverse DSFRFT.We denote,the multiplications and additions of t-SVD for calculating the DSFRFT ofAarelog2(n1n2)andrespectively.The multiplications and additions of t-SVD for calculating the DFT ofAareandn1n2n3log2(n1n2),respectively.Obviously,the additions for calculating the DSFRFT ofAis less than those of DFT.When log2(n1n2)>4,the multiplications for calculating the DSFRFT ofAis also less than those of DFT and the difference isThe computation complexity for calculating the SVD of the transformed matrixes and the inverse transform have the similar conclusions.Thus,additions and multiplications of our proposed t-SVD have lower computational cost compared with those of t-SVD based on DFT.

4 Conclusion

In this paper,we present definitions of t-product and t-SVD based on the DSFRFT.By applying the DSFRFT to deal with chirp tensors,the computation of t-product and t-SVD enjoy the conjugate symmetry and can be calculated more efficiently.Then,a new tensor nuclear norm can be defined induced by the DSFRFT based t-SVD.In addition,we analyze the computational complexity of the proposed t-SVD,and present the conclusion that the proposed t-SVD is at lower multiplication and addition complexity than those of the typical DFT based t-SVD.