GNGTS 2014 - Atti del 33° Convegno Nazionale

GNGTS 2014 S essione 3.1 2012) to solve the low-rank tensor completion problem with global optimization methods. In this work, we want to introduce a new greedy algorithm, called Orthogonal Rank-One Tensor Pursuit (OR1TP), that extends the Orthogonal Matching Pursuit (OMP) algorithm (Pati, 1993; Davis, 1994) that works in multidimensional tensor space and finds a low rank approximation of a tensor. We present a novel seismic interpolation algorithm based on the rank reduction technique, that solves the low-rank Hankel tensor completion problem in the frequency domain and that is capable to fill missing seismic traces in 3D dataset. Finally, we show experimental results obtained on synthetic data to prove the effectiveness of our method. Theory. A tensor is the generalization of vectors, matrices to higher dimensions. Let         be a N -th order tensor, while denotes the indexes of the observed entries of Y . The order N of a tensor is the number of dimensions, also known as ways or modes. A second-order tensor is a matrix and a first-order tensor is a vector. Let P Ω be the projector onto the space such that the indexes        . It is well known that the rank of a matrix coincides with its column and row rank. The rank of a tensor is a much trickier concept. The rank of a tensor Y is equal to the minimum number of rank-one tensors that yield Y in a linear combination. Any tensor        can be written as a linear combination of rank-one tensors, that is where     ,      are rank-one tensors such that            and r is the rank of the tensor Y . Rank-One tensor decomposition, also called Canonical Polyadic Decomposition (CPD; Zhang, 2001), gives a compact representation of the underlying structure of the tensor, revealing when the tensor-data can be modeled as lying close to a low dimensional subspace. The low-rank tensor completion problem aims to minimize the zero-norm of θ subject to the equality constraint          as follows: Unfortunately, direct (P0) norm minimization problem is NP - hard (nondeterministic polynomial time hard problem) because it is equivalent to a subset selection problem, which is itself an NP-hard combinatorial optimization problem (Donoho, 2004). Orthogonal Rank-One Tensor Pursuit. We can relax the original problem by rewriting (P0) as follows: The main idea is to extend the Orthogonal Matching Pursuit (OMP) procedure (Pati, 1993; Davis, 1994) from the vector field to the tensor field, introducing a novel greedy algorithm called Orthogonal Rank-One Tensor Pursuit ( OR1TP ) that solve (G0) problem in an efficient way. Following the idea proposed by (Wang, 2014), at each iteration a rank-one basis tensor is generated by the vectors that approximate the residual tensor of the data. After that, the weights of the current rank-one tensor bases are updated by performing an orthogonal projection of the