[Traitement du signal multi-antenne : Les décompositions tensorielles rejoignent l'échantillonnage compressé]
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.
Accepté le :
Publié le :
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
[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.
- Multi-Tree Compact Hierarchical Tensor Recurrent Neural Networks for Intelligent Transportation System Edge Devices, IEEE Transactions on Intelligent Transportation Systems, Volume 25 (2024) no. 8, p. 8719 | DOI:10.1109/tits.2024.3364250
- , ICASSP 2023 - 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2023), p. 1 | DOI:10.1109/icassp49357.2023.10097054
- Tensor Robust Principal Component Analysis From Multilevel Quantized Observations, IEEE Transactions on Information Theory, Volume 69 (2023) no. 1, p. 383 | DOI:10.1109/tit.2022.3198725
- 3D inverse synthetic aperture radar image quality improvement using sparse signal representation, IET Radar, Sonar Navigation, Volume 17 (2023) no. 3, p. 388 | DOI:10.1049/rsn2.12348
- Image reconstruction based on improved block compressed sensing, Computational and Applied Mathematics, Volume 41 (2022) no. 1, p. 18 (Id/No 4) | DOI:10.1007/s40314-021-01706-0 | Zbl:1499.94008
- Generalized Nonconvex Approach for Low-Tubal-Rank Tensor Recovery, IEEE Transactions on Neural Networks and Learning Systems, Volume 33 (2022) no. 8, p. 3305 | DOI:10.1109/tnnls.2021.3051650
- Triangular decomposition of CP factors of a third-order tensor with application to solving nonlinear systems of equations, Journal of Scientific Computing, Volume 90 (2022) no. 2, p. 25 (Id/No 74) | DOI:10.1007/s10915-021-01758-8 | Zbl:1481.15025
- Two-Dimensional DOA Estimation for Coprime Planar Arrays Based on Self-Correlation Tensor, Mathematical Problems in Engineering, Volume 2022 (2022), p. 1 | DOI:10.1155/2022/7999641
- Tensor Decomposition, Tensor Computation for Data Analysis (2022), p. 19 | DOI:10.1007/978-3-030-74386-4_2
- High order singular value decomposition for plant diversity estimation, Bollettino dell'Unione Matematica Italiana, Volume 14 (2021) no. 4, pp. 557-591 | DOI:10.1007/s40574-021-00300-w | Zbl:1505.65180
- Tensor-based approach for blind separation of interleave-NOMA 5G system, Scientific African, Volume 14 (2021), p. e00956 | DOI:10.1016/j.sciaf.2021.e00956
- Statistically optimal and computationally efficient low rank tensor completion from noisy entries, The Annals of Statistics, Volume 49 (2021) no. 1, pp. 76-99 | DOI:10.1214/20-aos1942 | Zbl:1473.62184
- Characterization of sampling patterns for low-tt-rank tensor retrieval, Annals of Mathematics and Artificial Intelligence, Volume 88 (2020) no. 8, pp. 859-886 | DOI:10.1007/s10472-020-09691-6 | Zbl:1466.62455
- Structured Alternating Minimization for Union of Nested Low-Rank Subspaces Data Completion, IEEE Journal on Selected Areas in Information Theory, Volume 1 (2020) no. 3, p. 632 | DOI:10.1109/jsait.2020.3039170
- Scalable Structured Compressive Video Sampling With Hierarchical Subspace Learning, IEEE Transactions on Circuits and Systems for Video Technology, Volume 30 (2020) no. 10, p. 3528 | DOI:10.1109/tcsvt.2019.2939370
- Analysis of the spatiotemporal riding modes of dockless shared bicycles based on tensor decomposition, International Journal of Geographical Information Science, Volume 34 (2020) no. 11, p. 2225 | DOI:10.1080/13658816.2020.1768259
- Union of low-rank tensor spaces: clustering and completion, Journal of Machine Learning Research (JMLR), Volume 21 (2020), p. 36 (Id/No 69) | Zbl:1499.62205
- On identifiability of higher order block term tensor decompositions of rank
rank-1, Linear and Multilinear Algebra, Volume 68 (2020) no. 2, pp. 223-245 | DOI:10.1080/03081087.2018.1502251 | Zbl:1429.15023 - Space-Time-Frequency Coding for MIMO Relay System Based on Tensor Decomposition, Radioelectronics and Communications Systems, Volume 63 (2020) no. 2, p. 77 | DOI:10.3103/s073527272002003x
- Пространственно-временное частотное кодирование на основе тензорного разложения для релейной системы MIMO, Известия высших учебных заведений. Радиоэлектроника, Volume 63 (2020) no. 2, p. 95 | DOI:10.20535/s002134702002003x
- , 2019 IEEE Congress on Evolutionary Computation (CEC) (2019), p. 1830 | DOI:10.1109/cec.2019.8790108
- , 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD) (2019), p. 1 | DOI:10.1109/iccad45719.2019.8942082
- , Big Data: Learning, Analytics, and Applications (2019), p. 22 | DOI:10.1117/12.2519095
- swTensor: accelerating tensor decomposition on Sunway architecture, CCF Transactions on High Performance Computing, Volume 1 (2019) no. 3-4, p. 161 | DOI:10.1007/s42514-019-00017-5
- Low-Rank Tensor Completion for Image and Video Recovery via Capped Nuclear Norm, IEEE Access, Volume 7 (2019), p. 112142 | DOI:10.1109/access.2019.2934482
- Deterministic and Probabilistic Conditions for Finite Completability of Low-Tucker-Rank Tensor, IEEE Transactions on Information Theory, Volume 65 (2019) no. 9, p. 5380 | DOI:10.1109/tit.2019.2919568
- Identifiability of complete dictionary learning, SIAM Journal on Mathematics of Data Science, Volume 1 (2019) no. 3, pp. 518-536 | DOI:10.1137/18m1233339 | Zbl:1513.68045
- Hankel tensor decompositions and ranks, SIAM Journal on Matrix Analysis and Applications, Volume 40 (2019) no. 2, pp. 486-516 | DOI:10.1137/18m1168285 | Zbl:1411.15018
- , 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP) (2018), p. 1363 | DOI:10.1109/globalsip.2018.8646430
- Completely positive tensor recovery with minimal nuclear value, Computational Optimization and Applications, Volume 70 (2018) no. 2, pp. 419-441 | DOI:10.1007/s10589-018-0003-5 | Zbl:1391.90465
- Compressive Sensing of Noisy 3-D Images Based on Threshold Selection, Journal of Advanced Computational Intelligence and Intelligent Informatics, Volume 22 (2018) no. 1, p. 70 | DOI:10.20965/jaciii.2018.p0070
- Set evincing the ranks with respect to an embedded variety (symmetric tensor rank and tensor rank), Mathematics, Volume 6 (2018) no. 8, p. 9 (Id/No 140) | DOI:10.3390/math6080140 | Zbl:1407.14053
- Nuclear norm of higher-order tensors, Mathematics of Computation, Volume 87 (2018) no. 311, pp. 1255-1281 | DOI:10.1090/mcom/3239 | Zbl:1383.15018
- A general theory of singular values with applications to signal denoising, SIAM Journal on Applied Algebra and Geometry, Volume 2 (2018) no. 4, pp. 535-596 | DOI:10.1137/17m1156149 | Zbl:1408.94861
- , 2017 51st Asilomar Conference on Signals, Systems, and Computers (2017), p. 305 | DOI:10.1109/acssc.2017.8335189
- , 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (2017), p. 604 | DOI:10.1109/allerton.2017.8262792
- , 2017 IEEE International Symposium on Information Theory (ISIT) (2017), p. 531 | DOI:10.1109/isit.2017.8006584
- , 2017 IEEE Symposium Series on Computational Intelligence (SSCI) (2017), p. 1 | DOI:10.1109/ssci.2017.8280968
- A tensor decomposition based multiway structured sparse SAR imaging algorithm with Kronecker constraint, Algorithms, Volume 10 (2017) no. 1, p. 17 (Id/No 2) | DOI:10.3390/a10010002 | Zbl:1461.94008
- Multi-linear sparse reconstruction for SAR imaging based on higher-order SVD, EURASIP Journal on Advances in Signal Processing, Volume 2017 (2017) no. 1 | DOI:10.1186/s13634-017-0479-7
- Structured Sparse Representation With Union of Data-Driven Linear and Multilinear Subspaces Model for Compressive Video Sampling, IEEE Transactions on Signal Processing, Volume 65 (2017) no. 19, p. 5062 | DOI:10.1109/tsp.2017.2721905
- Rank determination for low-rank data completion, Journal of Machine Learning Research (JMLR), Volume 18 (2017), p. 29 (Id/No 98) | Zbl:1441.65049
- On best rank-
and rank- approximations of order- tensors, Linear and Multilinear Algebra, Volume 65 (2017) no. 7, pp. 1289-1310 | DOI:10.1080/03081087.2016.1234578 | Zbl:1371.15024 - Symmetric tensor nuclear norms, SIAM Journal on Applied Algebra and Geometry, Volume 1 (2017) no. 1, pp. 599-625 | DOI:10.1137/16m1083384 | Zbl:1372.15023
- , 2016 Data Compression Conference (DCC) (2016), p. 181 | DOI:10.1109/dcc.2016.16
- , 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2016), p. 2966 | DOI:10.1109/icassp.2016.7472221
- On the nuclear norm and the singular value decomposition of tensors, Foundations of Computational Mathematics, Volume 16 (2016) no. 3, pp. 779-811 | DOI:10.1007/s10208-015-9264-x | Zbl:1343.15016
- Noisy Compressive Sampling Based on Block-Sparse Tensors: Performance Limits and Beamforming Techniques, IEEE Transactions on Signal Processing, Volume 64 (2016) no. 23, p. 6075 | DOI:10.1109/tsp.2016.2600510
- , 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) (2015), p. 53 | DOI:10.1109/camsap.2015.7383734
- , 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2015), p. 2454 | DOI:10.1109/icassp.2015.7178412
- Sparsity-Based Recovery of Finite Alphabet Solutions to Underdetermined Linear Systems, IEEE Transactions on Information Theory, Volume 61 (2015) no. 4, p. 2008 | DOI:10.1109/tit.2015.2399914
- Successive rank-one approximations for nearly orthogonally decomposable symmetric tensors, SIAM Journal on Matrix Analysis and Applications, Volume 36 (2015) no. 4, pp. 1638-1659 | DOI:10.1137/15m1010890 | Zbl:1330.15030
- Finding the limit of diverging components in three-way Candecomp/Parafac – a demonstration of its practical merits, Computational Statistics and Data Analysis, Volume 75 (2014), pp. 203-216 | DOI:10.1016/j.csda.2014.02.010 | Zbl:1506.62171
- CP decomposition approach to blind separation for DS-CDMA system using a new performance index, EURASIP Journal on Advances in Signal Processing, Volume 2014 (2014) no. 1 | DOI:10.1186/1687-6180-2014-128
- Compressive Sensing of Sparse Tensors, IEEE Transactions on Image Processing, Volume 23 (2014) no. 10, p. 4438 | DOI:10.1109/tip.2014.2348796
- Blind Multilinear Identification, IEEE Transactions on Information Theory, Volume 60 (2014) no. 2, p. 1260 | DOI:10.1109/tit.2013.2291876
- Short: Blind Separation of the Multiarray Multisensor Systems Using the CP Decomposition, Networked Systems, Volume 8593 (2014), p. 313 | DOI:10.1007/978-3-319-09581-3_22
- , 2013 IEEE International Conference on Multimedia and Expo (ICME) (2013), p. 1 | DOI:10.1109/icme.2013.6607560
- An upper bound for the tensor rank, ISRN Geometry, Volume 2013 (2013), p. 3 (Id/No 241835) | DOI:10.1155/2013/241835 | Zbl:1268.15026
- Grassmann secants, identifiability, and linear systems of tensors, Linear Algebra and its Applications, Volume 438 (2013) no. 1, pp. 121-135 | DOI:10.1016/j.laa.2012.07.045 | Zbl:1255.14044
- A Three-Way Jordan Canonical Form as Limit of Low-Rank Tensor Approximations, SIAM Journal on Matrix Analysis and Applications, Volume 34 (2013) no. 2, p. 624 | DOI:10.1137/120875806
- On the Uniqueness of the Canonical Polyadic Decomposition of Third-Order Tensors—Part I: Basic Results and Uniqueness of One Factor Matrix, SIAM Journal on Matrix Analysis and Applications, Volume 34 (2013) no. 3, p. 855 | DOI:10.1137/120877234
- A variational approach of the rank function, Top, Volume 21 (2013) no. 2, pp. 207-240 | DOI:10.1007/s11750-013-0283-y | Zbl:1269.49019
- Multidimensional compressed sensing and their applications, WIREs Data Mining and Knowledge Discovery, Volume 3 (2013) no. 6, p. 355 | DOI:10.1002/widm.1108
- Multi-Way Compressed Sensing for Sparse Low-Rank Tensors, IEEE Signal Processing Letters, Volume 19 (2012) no. 11, p. 757 | DOI:10.1109/lsp.2012.2210872
- Archetypal analysis for machine learning and data mining, Neurocomputing, Volume 80 (2012), p. 54 | DOI:10.1016/j.neucom.2011.06.033
- Candecomp/Parafac: From Diverging Components to a Decomposition in Block Terms, SIAM Journal on Matrix Analysis and Applications, Volume 33 (2012) no. 2, p. 291 | DOI:10.1137/110825327
- , 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (2011), p. 337 | DOI:10.1109/allerton.2011.6120187
- Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems, Mathematical Programming. Series A. Series B, Volume 129 (2011) no. 2 (B), pp. 357-382 | DOI:10.1007/s10107-011-0464-0 | Zbl:1230.90156
Cité par 69 documents. Sources : Crossref, zbMATH
Commentaires - Politique
Vous devez vous connecter pour continuer.
S'authentifier