GNGTS 2014 - Atti del 33° Convegno Nazionale

GNGTS 2014 S essione 3.1 65 The MPmethod approximates the representation of f by choosing one vector Φ k per iteration. In practice, at each iteration n , the algorithm selects the vector Φ k , which provides the highest contribution when correlated to the input data: (4) then the algorithm subtracts its contribution from residual data, and iterates this process until some stopping criterion is met. This approach has proved to be as accurate as the ALFT reference method while more efficient. By the way, it still has a drawback. As already observed, due to the irregularities in the input data sampling, the f-k representation of the data shows some energy leakage from true wavenumber components onto near components. This fact leads the algorithm, iteration after iteration, to pick the same component until all its leaked energy is consumed, which increases enormously the total number of iterations. Since the spectral leakage phenomenon is due to the non-orthogonality of the Fourier basis in case of irregular sampling, adding an orthogonalization step at each iteration would do the job. This method goes under the name of Orthogonal Matching Pursuit, OMP (Tropp and Gilbert, 2007) and has been applied in this context by Hollander et al. (2012). By the way, this approach leads to performing, at each iteration, an orthogonal projection of the input data onto the components selected so far, which is a very expensive procedure and highly increases the cost of a single iteration. The work of Blumensath and Davies (2009) addresses the challenge of finding a trade-off among number of iterations and cost per each iteration that would make this kind of approach even more efficient than the already explored MP. Interpolation via Stagewise Conjugate Gradient Pursuit. The proposed approach introduces two main improvements (Blumensath and Davies, 2009), which both bring advantages in reducing computational costs: the Stagewise strategy, which selects more than a single coefficients at each iteration, and the Conjugate Gradient Pursuit which updates at each iteration the coefficient selected so far by a conjugate direction. For what concerns the stagewise selection, the generalization is straightforward. While both ALFT and MP propose to select, at each iteration, a single Fourier component, this method proposes to take a number of components.Apart from the different number of coefficients selected per iteration, the selection strategy is the same as in MP: the wavenumbers which provide the highest energy contribute are taken and added to the set of components collected so far. For what concerns the update direction, Blumensath and Davies (2009) recall that the usage of a conjugate gradient direction offers significant advantages in terms of computational costs if compared to OMP, while still providing convergence guarantees. Thus, at each iteration, after that the set of new components is selected and the respective contribute to the data representation evaluated, an updating constant is computed such that consecutive directions are conjugate. Of course, being not an exact orthogonalization performed at each iteration, same coefficients can be re-selected iteration after iteration. Blumensath and Davies (2009) underline that this method has an intrinsic mechanism that senses how orthogonal all previously selected components are with respect to the residual. If they are far from orthogonal, the inner products will give a large result in magnitude and a component will be re-selected. Otherwise, if after a single updating step the components are nearly orthogonal to the residual, then the algorithm will not re-select the same components. Practical issues. Some discussion is due about the actual implementation of the presented interpolation tool. For what concerns the number of Fourier components selected at each iteration, experiments suggest tuning this parameter depending on the amount of irregularity which affects the input data sampling. In fact, the more irregular the sampling is, the more the amount of leaked energy is, and the lower the number of components selected per iteration should be.