Comptes Rendus
no. 6
Multiarray signal processing: Tensor decomposition meets compressed sensing
[Traitement du signal multi-antenne : Les décompositions tensorielles rejoignent l'échantillonnage compressé]

Présenté par : Odile Macchi

Lek-Heng Lim1 ; Pierre Comon2 
1 Department of Mathematics, University of California, Berkeley, CA 94720-3840, United States
2 Laboratoire I3S, CNRS UMR6070, University of Nice, 06903, Sophia-Antipolis, France
Comptes Rendus. Mécanique, Volume 338 (2010) no. 6, pp. 311-320.

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.

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.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crme.2010.06.005
Keywords: Signal processing, Blind source separation, Blind channel identification, Tensors, Tensor rank, Polyadic tensor decompositions, Best rank-r approximations, Sparse representations, Spark, k-rank, Coherence, Multiarrays, Multisensors
Mot 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

1 Department of Mathematics, University of California, Berkeley, CA 94720-3840, United States
2 Laboratoire I3S, CNRS UMR6070, University of Nice, 06903, Sophia-Antipolis, France 
@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},
}
TY  - JOUR
AU  - Lek-Heng Lim
AU  - Pierre Comon
TI  - Multiarray signal processing: Tensor decomposition meets compressed sensing
JO  - Comptes Rendus. Mécanique
PY  - 2010
SP  - 311
EP  - 320
VL  - 338
IS  - 6
PB  - Elsevier
DO  - 10.1016/j.crme.2010.06.005
LA  - en
ID  - CRMECA_2010__338_6_311_0
ER  - 
%0 Journal Article
%A Lek-Heng Lim
%A Pierre Comon
%T Multiarray signal processing: Tensor decomposition meets compressed sensing
%J Comptes Rendus. Mécanique
%D 2010
%P 311-320
%V 338
%N 6
%I Elsevier
%R 10.1016/j.crme.2010.06.005
%G en
%F CRMECA_2010__338_6_311_0
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] E.J. Candès Compressive sampling, Int. Congress Math., Volume III (2006), pp. 1433-1452

[2] E.J. Candès; J. Romberg Sparsity and incoherence in compressive sampling, Inverse Problems, Volume 23 (2007) no. 3, pp. 969-985

[3] A. Cohen; W. Dahmen; R. DeVore Compressed sensing and best k-term approximation, J. Amer. Math. Soc., Volume 22 (2009) no. 1, pp. 211-231

[4] D.L. Donoho Compressed sensing, IEEE Trans. Inform. Theory, Volume 52 (2006) no. 4, pp. 1289-1306

[5] D.L. Donoho; M. Elad Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ1 minimization, Proc. Nat. Acad. Sci., Volume 100 (2003) no. 5, pp. 2197-2202

[6] R. Gribonval; M. Nielsen Sparse representations in unions of bases, IEEE Trans. Inform. Theory, Volume 49 (2003) no. 12, pp. 3320-3325

[7] E.J. Candès; B. Recht 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] M. Fazel; H. Hindi; S. Boyd A rank minimization heuristic with application to minimum order system approximation, Proc. Amer. Control Conf., Volume 6 (2001), pp. 4734-4739

[10] D. Gross Recovering low-rank matrices from few coefficients in any basis, 2009 (preprint) | arXiv

[11] B. Recht; M. Fazel; P. Parrilo 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] J. Rhodes A concise proof of Kruskal's theorem on tensor decomposition, Linear Algebra Appl., Volume 432 (2010) no. 7, pp. 1818-1824

[14] P. Comon; G. Golub; L.-H. Lim; B. Mourrain Symmetric tensors and symmetric tensor rank, SIAM J. Matrix Anal. Appl., Volume 30 (2008) no. 3, pp. 1254-1279

[15] V. De Silva; L.-H. Lim 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] J. Håstad Tensor rank is NP-complete, J. Algorithms, Volume 11 (1990) no. 4, pp. 644-654

[17] C. Hillar; L.-H. Lim Most tensor problems are NP-hard, 2009 (preprint) | arXiv

[18] P. Comon, L.-H. Lim, Sparse representations and tensor decompositions, preprint, 2010.

[19] E.J. Candès 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] J. Tropp Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inform. Theory, Volume 50 (2004) no. 10, pp. 2231-2242

[21] P. Comon 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] M. Duarte; M. Davenport; D. Takhar; J. Laska; T. Sun; K. Kelly; R. Baraniuk Single-pixel imaging via compressive sampling, IEEE Signal Process. Mag., Volume 25 (2008) no. 2, pp. 83-91

[24] N.D. Sidiropoulos; R. Bro; G.B. Giannakis Parallel factor analysis in sensor array processing, IEEE Trans. Signal Process., Volume 48 (2000) no. 8, pp. 2377-2388

[25] R. Roy; A. Paulraj; T. Kailath 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] F.L. Hitchcock 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] L.-H. Lim; P. Comon Nonnegative approximations of nonnegative tensors, J. Chemometrics, Volume 23 (2009) no. 7–8, pp. 432-441

[28] M.V. Catalisano; A.V. Geramita; A. Gimigliano Ranks of tensors, secant varieties of Segre varieties and fat points, Linear Algebra Appl., Volume 355 (2002) no. 1–3, pp. 263-285

[29] J.M. Landsberg; L. Manivel On the ideals of secant varieties of Segre varieties, Found. Comput. Math., Volume 4 (2004) no. 4, pp. 397-422

[30] F.L. Zak Tangents and Secants of Algebraic Varieties, AMS, Providence, RI, 1993

[31] J.-B. Hiriart-Urruty; C. Lemaréchal Convex Analysis and Minimization Algorithms, I & II, Springer-Verlag, Berlin, 1993

[32] J.G. Oxley Matroid Theory, Oxford University Press, New York, NY, 1992

[33] J.B. Kruskal 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] A. Vardy The intractability of computing the minimum distance of a code, IEEE Trans. Inform. Theory, Volume 43 (1997) no. 6, pp. 1757-1766

[35] B.K. Natarajan Sparse approximate solutions to linear systems, SIAM J. Comput., Volume 24 (1995) no. 2, pp. 227-234

[36] J.M. Landsberg Kruskal's theorem, 2009 (preprint) | arXiv

[37] A. Stegeman; N.D. Sidiropoulos 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.

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Average performance of the approximation in a dictionary using an ℓ0 objective

François Malgouyres; Mila Nikolova

C. R. Math (2009)