We analyze the decomposition problem of multivariate polynomial-exponential functions from truncated series and present new algorithms to compute their decomposition. Using the duality between polynomials and formal power series, we first show how the elements in the dual of an Artinian algebra correspond to polynomial-exponential functions. They are also the solutions of systems of partial differential equations with constant coefficients. We relate their representation to the inverse system of the roots of the characteristic variety. Using the properties of Hankel operators, we establish a correspondence between polynomial exponential series and Artinian Gorenstein algebras. We generalize Kronecker theorem to the multivariate case, by showing that the symbol of a Hankel operator of finite rank is a polynomial-exponential series and by connecting the rank of the Hankel operator with the decomposition of the symbol. A generalization of Prony's approach to multivariate decomposition problems is presented , exploiting eigenvector methods for solving polynomial equations. We show how to compute the frequencies and weights of a minimal polynomial-exponential decomposition , using the first coefficients of the series. A key ingredient of the approach is the flat extension criteria, which leads to a multivariate generalization of a rank condition for a Carath 'e odory-Fej 'e r decomposition of multivariate Hankel matrices. A new algorithm is given to compute a basis of the Artinian Gorenstein algebra, based on a Gram-Schmidt orthogonalization process and to decompose polynomial-exponential series. A general framework for the applications of this approach is described and illustrated in different problems. We provide Kronecker-type theorems for convolution operators, showing that a convolution operator (or a cross-correlation operator) is of finite rank, if and only if, its symbol is a polynomial-exponential function, and we relate its rank to the decomposition of its symbol. We also present Kronecker-type theorems for the reconstruction of measures as weighted sums of Dirac measures from moments and for the decomposition of polynomial-exponential functions from values. Finally, we describe an application of this method for the sparse interpolation of polylog functions from values.
A completely different approach, known as compressive sensing , has been developed over the last decades to compute sparse decompositions of functions (see e.g. @cite_1 ). In this approach, a (large) dictionary of functions is chosen and a sparse combination with few non-zero coefficients is computed from some observations. This boils to find a sparse solution @math of an underdetermined linear system @math . Such a solution, which minimizes the @math norm'' can be computed by @math minimization, under some hypothesis.
@cite_1
2164452299
In this paper, a fast algorithm for overcomplete sparse decomposition, called SL0, is proposed. The algorithm is essentially a method for obtaining sparse solutions of underdetermined systems of linear equations, and its applications include underdetermined sparse component analysis (SCA), atomic decomposition on overcomplete dictionaries, compressed sensing, and decoding real field codes. Contrary to previous methods, which usually solve this problem by minimizing the l 1 norm using linear programming (LP) techniques, our algorithm tries to directly minimize the l 1 norm. It is experimentally shown that the proposed algorithm is about two to three orders of magnitude faster than the state-of-the-art interior-point LP solvers, while providing the same (or better) accuracy. Consider the recovery of an unknown signal @math from quantized linear measurements. In the one-bit compressive sensing setting, one typically assumes that @math is sparse, and that the measurements are of the form @math . Since such measurements give no information on the norm of @math , recovery methods typically assume that @math . We show that if one allows more generally for quantized affine measurements of the form @math , and if the vectors @math are random, an appropriate choice of the affine shifts @math allows norm recovery to be easily incorporated into existing methods for one-bit compressive sensing. In addition, we show that for arbitrary fixed @math in the annulus @math , one may estimate the norm @math up to additive error @math from @math such binary measurements through a single evaluation of the inverse Gaussian error function. Finally, all of our recovery guarantees can be made universal over sparse vectors in the sense that with high probability, one set of measurements and thresholds can successfully estimate all sparse vectors @math in a Euclidean ball of known radius. Consider the recovery of an unknown signal @math from quantized linear measurements. In the one-bit compressive sensing setting, one typically assumes that @math is sparse, and that the measurements are of the form @math . Since such measurements give no information on the norm of @math , recovery methods from such measurements typically assume that @math . We show that if one allows more generally for quantized affine measurements of the form @math , and if the vectors @math are random, an appropriate choice of the affine shifts @math allows norm recovery to be easily incorporated into existing methods for one-bit compressive sensing. Additionally, we show that for arbitrary fixed @math in the annulus @math , one may estimate the norm @math up to additive error @math from @math such binary measurements through a single evaluation of the inverse Gaussian error function. Finally, all of our recovery guarantees can be made universal over sparse vectors, in the sense that with high probability, one set of measurements and thresholds can successfully estimate all sparse vectors @math within a Euclidean ball of known radius. We consider a linear stochastic bandit problem where the dimension @math of the unknown parameter @math is larger than the sampling budget @math . In such cases, it is in general impossible to derive sub-linear regret bounds since usual linear bandit algorithms have a regret in @math . In this paper we assume that @math is @math sparse, i.e. has at most @math non-zero components, and that the space of arms is the unit ball for the @math norm. We combine ideas from Compressed Sensing and Bandit Theory and derive algorithms with regret bounds in @math .