We discuss how recently discovered techniques and tools from compressed sensing can be used in tensor decompositions, with a view towards modeling signals from multiple arrays of multiple sensors. We show that with appropriate bounds on a measure of separation between radiating sources called coherence, one could always guarantee the existence and uniqueness of a best rank-r approximation of the tensor representing the signal. We also deduce a computationally feasible variant of Kruskal's uniqueness condition, where the coherence appears as a proxy for k-rank. Problems of sparsest recovery with an infinite continuous dictionary, lowest-rank tensor representation, and blind source separation are treated in a uniform fashion. The decomposition of the measurement tensor leads to simultaneous localization and extraction of radiating sources, in an entirely deterministic manner.
Nous décrivons comment les techniques et outils d'échantillonnage compressé récemment découverts peuvent être utilisés dans les décompositions tensorielles, avec pour illustration une modélisation des signaux provenant de plusieurs antennes multicapteurs. Nous montrons qu'en posant des bornes appropriées sur une certaine mesure de séparation entre les sources rayonnantes (appelée cohérence dans le jargon de l'échantillonnage compressé), on pouvait toujours garantir l'existence et l'unicité d'une meilleure approximation de rang r du tenseur représentant le signal. Nous en déduisons aussi une variante calculable de la condition d'unicité de Kruskal, où cette cohérence apparaît comme une mesure du k-rang. Les problèmes de récupération parcimonieuse avec un dictionnaire infini continu, de représentation tensorielle de plus bas rang, et de séparation aveugle de sources sont ainsi abordés d'une seule et même façon. La décomposition du tenseur de mesures conduit à la localisation et à l'extraction simultanées des sources rayonnantes, de manière entièrement déterministe.
Accepted:
Published online:
Mots-clés : Traitement de signal, Séparation aveugle de sources, Identification aveugle de canal, Tenseurs, Rang tensoriel, Décompositions tensorielles polyadiques, Meilleure approximation de rang r, Représentations parcimonieuses, Spark, k-rang, Cohérence, Antennes multiples, Multicapteurs
Lek-Heng Lim 1; Pierre Comon 2
@article{CRMECA_2010__338_6_311_0, author = {Lek-Heng Lim and Pierre Comon}, title = {Multiarray signal processing: {Tensor} decomposition meets compressed sensing}, journal = {Comptes Rendus. M\'ecanique}, pages = {311--320}, publisher = {Elsevier}, volume = {338}, number = {6}, year = {2010}, doi = {10.1016/j.crme.2010.06.005}, language = {en}, }
Lek-Heng Lim; Pierre Comon. Multiarray signal processing: Tensor decomposition meets compressed sensing. Comptes Rendus. Mécanique, Volume 338 (2010) no. 6, pp. 311-320. doi : 10.1016/j.crme.2010.06.005. https://comptes-rendus.academie-sciences.fr/mecanique/articles/10.1016/j.crme.2010.06.005/
[1] Compressive sampling, Int. Congress Math., Volume III (2006), pp. 1433-1452
[2] Sparsity and incoherence in compressive sampling, Inverse Problems, Volume 23 (2007) no. 3, pp. 969-985
[3] Compressed sensing and best k-term approximation, J. Amer. Math. Soc., Volume 22 (2009) no. 1, pp. 211-231
[4] Compressed sensing, IEEE Trans. Inform. Theory, Volume 52 (2006) no. 4, pp. 1289-1306
[5] Optimally sparse representation in general (nonorthogonal) dictionaries via minimization, Proc. Nat. Acad. Sci., Volume 100 (2003) no. 5, pp. 2197-2202
[6] Sparse representations in unions of bases, IEEE Trans. Inform. Theory, Volume 49 (2003) no. 12, pp. 3320-3325
[7] Exact matrix completion via convex optimization, Found. Comput. Math., Volume 9 (2009) no. 6, pp. 717-772
[8] E.J. Candès, T. Tao, The power of convex relaxation: Near-optimal matrix completion, preprint, 2009.
[9] A rank minimization heuristic with application to minimum order system approximation, Proc. Amer. Control Conf., Volume 6 (2001), pp. 4734-4739
[10] Recovering low-rank matrices from few coefficients in any basis, 2009 (preprint) | arXiv
[11] Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, 2008 (preprint) | arXiv
[12] Z. Zhu, A.M.-C. So, Y. Ye, Fast and near-optimal matrix completion via randomized basis pursuit, preprint, 2009.
[13] A concise proof of Kruskal's theorem on tensor decomposition, Linear Algebra Appl., Volume 432 (2010) no. 7, pp. 1818-1824
[14] Symmetric tensors and symmetric tensor rank, SIAM J. Matrix Anal. Appl., Volume 30 (2008) no. 3, pp. 1254-1279
[15] Tensor rank and the ill-posedness of the best low-rank approximation problem, SIAM J. Matrix Anal. Appl., Volume 30 (2008) no. 3, pp. 1084-1127
[16] Tensor rank is NP-complete, J. Algorithms, Volume 11 (1990) no. 4, pp. 644-654
[17] Most tensor problems are NP-hard, 2009 (preprint) | arXiv
[18] P. Comon, L.-H. Lim, Sparse representations and tensor decompositions, preprint, 2010.
[19] The restricted isometry property and its implications for compressed sensing, C. R. Math. Acad. Sci. Paris, Volume 346 (2008) no. 9–10, pp. 589-592
[20] Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inform. Theory, Volume 50 (2004) no. 10, pp. 2231-2242
[21] Contrasts, independent component analysis, and blind deconvolution, Int. J. Adapt. Control Signal Process., Volume 18 (2004) no. 3, pp. 225-243
[22] Handbook of Blind Source Separation: Independent Component Analysis and Applications (P. Comon; C. Jutten, eds.), Academic Press, New York, NY, 2010
[23] Single-pixel imaging via compressive sampling, IEEE Signal Process. Mag., Volume 25 (2008) no. 2, pp. 83-91
[24] Parallel factor analysis in sensor array processing, IEEE Trans. Signal Process., Volume 48 (2000) no. 8, pp. 2377-2388
[25] ESPRIT — A subspace rotation approach to estimation of parameters of cisoids in noise, IEEE Trans. Acoust. Speech Signal Process., Volume 34 (1986) no. 5, pp. 1340-1344
[26] The expression of a tensor or a polyadic as a sum of products, J. Math. Phys., Volume 6 (1927) no. 1, pp. 164-189
[27] Nonnegative approximations of nonnegative tensors, J. Chemometrics, Volume 23 (2009) no. 7–8, pp. 432-441
[28] Ranks of tensors, secant varieties of Segre varieties and fat points, Linear Algebra Appl., Volume 355 (2002) no. 1–3, pp. 263-285
[29] On the ideals of secant varieties of Segre varieties, Found. Comput. Math., Volume 4 (2004) no. 4, pp. 397-422
[30] Tangents and Secants of Algebraic Varieties, AMS, Providence, RI, 1993
[31] Convex Analysis and Minimization Algorithms, I & II, Springer-Verlag, Berlin, 1993
[32] Matroid Theory, Oxford University Press, New York, NY, 1992
[33] Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics, Linear Algebra Appl., Volume 18 (1977) no. 2, pp. 95-138
[34] The intractability of computing the minimum distance of a code, IEEE Trans. Inform. Theory, Volume 43 (1997) no. 6, pp. 1757-1766
[35] Sparse approximate solutions to linear systems, SIAM J. Comput., Volume 24 (1995) no. 2, pp. 227-234
[36] Kruskal's theorem, 2009 (preprint) | arXiv
[37] On Kruskal's uniqueness condition for the candecomp/parafac decomposition, Linear Algebra Appl., Volume 420 (2007) no. 2–3, pp. 540-552
[38] H. Derksen, Sharpness of Kruskal's theorem, preprint, 2009.
Cited by Sources:
Comments - Policy