On the Minimum Perimeter Criterion for Bounded Component Analysis

Depósito de Investigación de la Universidad de Sevilla https://idus.us.es/ This is a accepted version of a Conference by IEEE: IEEE Int. Conference on Acoustics, Speech and Signal Processing (ICASSP 2023), Rhodes Island, Greece, 4-9 June 2023. , available at: 10.1109/ICASSP49357.2023.10096945 “© 2023 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.” ON THE MINIMUM PERIMETER CRITERION FOR BOUNDED COMPONENT ANALYSIS Sergio Cruces∗ Dept. Teor´ ıa de la Se˜ nal y Comunicaciones Escuela de Ingenieros Universidad de Sevilla, Spain. sergio (at) us (dot) es ABSTRACT Bounded component analysis refers to a set of unsupervised techniques for the identification and recovery of underlying components of observations whose support has clear boundaries. This contribution is focused on the statistical justification and practical implementation of the minimum perimeter criterion, a bounded component analysis technique that can be used for the extraction of complex signals. In particular, with the help of the isoperimetric inequality, we reveal the link of the robust optimization of a statistical risk function with this criterion. We also address the difficulties for its optimization since, at the separation solutions, the criterion is nondifferentiable. A reformulation of its optimization is shown to lead to a practical implementation that, for sources with clear boundaries, outperforms the normalized MSE performance of the state-of-the-art blind separation methods, being even close to the optimal performance of supervised methods. Index Terms—Bounded component analysis, blind source separation, independent component analysis. 1. INTRODUCTION The unsupervised decomposition of the observations into a set of additive latent components is a problem with many applications in scientific and practical fields [1]-[3]. During the last decades, several families of techniques have exploited the structural properties of the components to recover them, such as independent component analysis, nonnegative matrix factorizations, low-rank decompositions, and sparse coding, to name just a few of them. Within this context, the term bounded component analysis (BCA) was coined to refer to a group of techniques [6]–[17] that rely on the bounded nature of the latent signals or sources for their estimation. Although most BCA methods address the case of linear mixtures with real values, this contribution focuses on the minimum perimeter criterion for BCA [13], an algorithm which naturally extends the criteria of minimum range or ∗Work supported by the grants: PID2021-123090NB-I00 and TEC2017- 82807-P, funded by MCIN/AEI/10.13039/501100011033/FEDER, UE; PAIDI Andalucian grants P20 01173 and US-1264994/ FEDER, UE. minimum zero-order entropy to situations of linear mixtures in the field of complex numbers. A cornerstone of component analysis methods are the identifiability, trivial indeterminacies, and separability properties [4]-[5]. In bounded component analysis, these properties can be guaranteed under some mild BCA hypotheses (see [13]-[15]) that do not require the mutual independence of the sources [16]-[17]. This paper is structured as follows. Section 2 defines the signal model, section 3 presents a statistical justification for the minimum perimeter criterion, section 4 analyzes its optimization, section 5 provides exemplary simulations, while the conclusions, in section 6, summarize our contribution. Due to the space limitations, we have to omit the detailed proofs, which will be provided in an extended version of this work. 2. SIGNAL MODEL AND NOTATION Since a necessary condition for separability of Nsources in BCA is the full column-rank property of the mixing matrix, without loss of generality, we assume the prewhitening and centering of the i.i.d. random vectors of measurements. Hence, we can drop the time index and define the linear noisy model of preprocessed observations x= [x1, . . . , xN]T=A s +e,(1) where the vector s= [s1, . . . , sN]∈CNgathers the bounded sources, A∈CN×Ndenotes the square mixing matrix after whitening, and the vector erefers to a residual noise term. The separation matrix B= [b1,...,bN]H∈CN×Nprovides the outputs or estimated source signals y= [y1, . . . , yN]T=B x.(2) The whitening of the sequence of observations makes the sample covariance matrix ˆ Σxequal to the identity matrix. Due to their algorithmic advantages, it is usually adopted together with a unitary constraint on B(e.g. [18]), which ensures the decorrelation of the outputs sequence ˆ Σy=I. In our case, we will not enforce this later constraint since it would imply a limit in the achievable performance, because the sources in finite samples are typically slightly correlated. The perimeter L(yi)of the output random variable yi is defined as the frontier length of the convex hull of its support set. In practice, there are efficient algorithms that compute the convex hull of the output sequence of samples yn i≡ {yi[1], . . . , yi[n])}and return a circular array of indexes [κ0, κ1, . . . , κV], with κ0=κV, which determine the position in (counterclockwise order) of the vertex of the convex hull: {y1[κ1], . . . , y1[κV]}. The sample perimeter of the i-th output is then computed as the following length ˆ L(yi) = V X v=1 (y1[κv]−y1[κv−1]).(3) 3. STATISTICAL JUSTIFICATION Given the set of perimeter statistics of the outputs T(B) = {L(y1),· · · , L(yN)}(4) and the evidence gathered from their sample estimates ˆ T(B) = nˆ L(y1),· · · ,ˆ L(yN)o(5) we consider the linear family of distributions D(B) = np(x) : T(B) = ˆ T(B)o.(6) We adopt as statistical loss function for the estimate of the density of the observations ˆq≡ˆq(x) = Qn t=1 q(x[t]) the cross-entropy estimation risk R(q: ˆq;B) = Zq(x|p→D(B)) log 1 ˆq(x)dx,(7) where q≡q(x|p→D(B))refers to the projection of the unknown data generating distribution ponto the manifold D(B). Under certain regularity conditions, the best-worst-case cross-entropy risk leads to an specific projection q?∈ D(B) as well as to the robust density estimate ˆq?(x)that maximizes the entropy of the observations h(ˆq(x)). Therefore, given the perimeter measurements in (5), we have shown that the robust density estimate of the observations simplifies to the factorized density ˆq?(x) = |BBH| N Y i=1 p◦(yi),(8) where |BBH|refers to the determinant of BBH, and the marginal density of each i-th complex output is uniform and ball-shaped (a disk B(0, ri)in C), i.e., p◦(yi) =    4π ˆ L2(yi)yi∈ B (0, ri) 0otherwise, (9) Here, as a consequence of the isoperimetric inequality [19], the disk radius is ri=ˆ L(yi) 2π= max ˆ A(yi) π! 1 2 ,(10) because it is the one that maximizes the entropy h(p◦(yi)) for a given value of ˆ L(yi). This is better observed in terms of the maximization of the area ˆ A(yi)of the minimum convex cover that supports the output sequence yn i. Theorem 1 (Statistical justification of the criterion) For the robust density estimate in (8), one reaches the equilibrium value of the minimax estimation risk R(q: ˆq;B), which adopts the following expression R(q?: ˆq?;B) = 2 log C(B)−log 4π+ log |ˆ Σx|,(11) where C(B)is recognized as the scale and permutation invariant contrast function of the “minimum perimeter criterion” for bounded component analysis, that is, C(B) = QN i=1 ˆ L(yi) |ˆ Σy|1 2 .(12) From (11), it follows the proportionality relation (through a monotonically increasing transformation) C(B)∝exp R(q?: ˆq?;B) 2(13) that provides the sought statistical justification for the “minimum perimeter criterion”. In this sense, it implicitly minimizes the best-worst-case cross-entropy risk when estimating the model of the observations. 4. OPTIMIZATION OF THE CRITERION The optimization of the minimum perimeter criterion, see (12), has the special difficulty that the desired solutions belong to subspaces where the contrast function is nondiffentiable. The algorithm proposed in [13] for its optimization was based on a projected gradient descent method with an optimized Newton-Raphson step-size selection [13]. While this algorithm seems to work quite well in low-dimensional scenarios, in more complex situations, its convergence can get stuck in the vicinity nondifferentiable subspaces, rendering it impractical for medium and large-scale problems. The purpose of this section is to reformulate the optimization of the minimum perimeter criterion (see (12)) in terms of the equivalent constrained maximization problem maximize |ˆ Σy|1 2subject to ˆ L(yi)≤1, j = 1, . . . , N, (14) as well as to propose an optimization algorithm that improves the convergence to the separation solutions. This goal forces us to dig deeper into the properties of L(yj)and |Σy|1 2, the relevant statistics of the output random vector. With this aim, we have proved the following convexity results. Lemma 1 (Convexity of the perimeter) Given the parameterized separation matrix B(λ), where λ∈[0,1], and its corresponding outputs y(λ) = B(λ)x, consider a noiseless scenario and the convex combinations B(λ) = λB(1) + (1 −λ)B(0),(15) y(λ) = λy(1) + (1 −λ)y(0).(16) Under the BCA hypotheses for identifiability (see [13, 14]) the perimeter of each output L(yj)is a convex function, where L(yj(λ)) ≤(1 −λ)L(yj(0)) + λ L(yj(1)),(17) with equality only for λ∈ {0,1}or when the elements of the global transfer systems gH j(0) = bH j(0)Aand gH j(1) = bH j(1)A(18) share identical complex signs in a component-wise fashion: sign(gj(0)) = sign(gj(1)). Lemma 2 (Partial convexity of |Σy|1/2)In subspaces that keep constant all but one of the outputs, the square root of the determinant of the output covariance matrix is a convex function. Therefore, provided that B(0) and B(1) differ only in a single row, for λ∈[0,1], the following inequality is satisfied |Σy(λ)|1/2≤λ|Σy(1)|1/2+ (1 −λ)|Σy(0)|1/2.(19) In scenarios with sufficient large samples and high signal- to-noise ratios, the previous lemmas also apply asymptotically to the sample statistics of the outputs ˆ L(yj)and |ˆ Σy|1/2. Under these conditions, the following result is obtained. Theorem 2 (BCA contrast functions) Provided that the BCA hypotheses hold for sufficiently large samples, the contrained local maxima of each one of the functions fj(bj)≡f([b1,...,bj,...,bN]) = |ˆ Σy|1/2(20) subject to ˆ L(bH jx)≤1,(21) with respect to the row bH j, j ∈[1, N],of the separation system B= [b1,...,bN]H, while being the other rows bH kfixed ∀k6=j, can only occur at the recovery of one of the sources. In plain words, the theorem tells us that the partial optimization of the criterion with respect to each row of the separation matrix is a contrast function without spurious local maxima (those that do not recover one of the sources). This result paves our way for the proposal of a block coordinate ascent constrained maximization technique that sequentially optimizes (20) subject to (21) with respect to each column of BH, while keeping the remaining columns fixed. The pseudo-code of the proposed (block) coordinate ascent algorithm for the blind separation of all sources is shown Algorithm 1 Block coordinate ascent optimization. initialize BH= [b1,...,bN]and B∗=B while not convergence for j= 1,...,N bj= arg local maximiz. fj(bj) subject to ˆ L(bH jx)≤1 # keep track of the best found solution. if f(BH)> f(BH ∗)then B∗=B end end end in Algorithm 1. A hierarchical implementation that extracts the sources one by one is also possible, although, we will not discuss it here. The core of the proposal is the local maximization of each fj(bj)under affine inequality constraint, which is implemented through a minorization maximization technique together with an alternating projection method onto affine subspaces to obtain the feasible solutions. The exact details of the implementation go beyond the scope of this communication. However, for a fast convergence, one should initially use larger step-sizes that allow us to reach the neighborhood of the separation solutions, and later progressively cool them to favor the convergence. The use of fast step-sizes does not guarantee the monotonic ascent in the objective function, hence, the algorithm keeps track of the best candidate solution B∗that has been obtained so far. 5. SIMULATIONS An exemplary simulation will illustrate the advantages of the proposed scheme for the implementation of the minimum perimeter criterion of bounded components analysis. Subfigure 1(a) favorably compares the proposal with other well-known unsupervised techniques for the linear separation of complex signals. These state-of-the-art techniques are: JADE [20], ACMA [21], CMN-FASTICA [22], Robust- ICA [23], and a previous technique for the optimization of the minimum perimeter criterion [13]. The chosen performance metric is the expected normalized mean squared error (NMSE), which measures the quality in the recovery of the source signals. It is averaged over 100 Monte Carlo simulations of noisy and complex 10 ×10 mixtures of ten communication sources, with a length of n= 300 samples. In each run the mixture is random, while the sources are individually drawn with equiprobability from these modulations: 32- APSK (amplitude-phase shift keying) or a 16-QAM (quadrature amplitude modulation). A meaningfull comparison in NMSE performance between the unsupervised algorithms, requires some extra information about the sources that can be used to estimate their complex scaling and inherent permutation indeterminacies. For simplicity, we have used the first three symbols of each source to fix the scaling and rotation alignment of the constellation. However, note that this kind of alignment could also be performed blindly if knowledge of the constellation is used to find the right scaling and differential encoding is employed to transmit the information. This kind of encoding is immune to any possible rotation indeterminacy that preserves the original shape of the constellation. We also used fifty symbols per source for solving the permutation ambiguity of the sources, since, with high probability, these are enough for a meaningful and well-aligned comparison between the transmitted and estimated signals. The results in Figure 1(a) illustrate how the unsupervised method “Proposed BCA” (the blue triangles) clearly outperforms in NMSE the remaining unsupervised techniques, being, for moderate and high SNRs, close to the optimal NMSE performance of the Wiener filtering (a supervised method). The favourable behaviour of the proposal with respect to other BSS methods, relays on the improved accuracy for the estimated perimeter/support of signals with clear boundaries (especially in situations of high-SNR and small samples) in comparison with those statistics exploited by other techniques. Since the proposed algorithm already provides a good separation system, inspired by what in equalization is known as the “decision directed mode”, we can apply a semisupervised postprocessing that takes advantage of prior knowledge of the constellation of the sources to make a provisional hard decision of the separated symbols. These detected symbols are then used as training pilots to reestimate a Wiener MIMO filter that mitigates the noise, yielding the result presented in Subfigure 1(b) under the label “PROPOSED BCA + Post-processing”. Subfigure 1(b) compares the performance of this semi-supervised proposal with the one of supervised methods trained on the full extension of the sources. One can observe that, as the signal-to-noise ratio improves, the post-processing of the BCA proposal can progressively reach the optimal NMSE performance of supervised methods. 6. CONCLUSIONS We have presented a statistical justification for the minimum perimeter criterion of bounded component analysis and developed an improved technique for its optimization. The simulations reveal that, in communications scenarios where the BCA hypotheses are usually satisfied, this proposal clearly outperforms the state-of-the-art methods for the blind source separation of complex signals. Moreover, for moderate and high signal-to-noise ratios, the performance of this blind technique is close to the optimal one achieved by supervised methods. 0 10 20 30 40 50 60 SNR [dB] -50 -40 -30 -20 -10 0 10 NMSE [dB] ROBUST-ICA JADE ACMA CMN-FASTICA previous BCA PROPOSED BCA OPTIMAL NMSE (supervised) (a) Performance of blind methods w.r.t. the optimal NMSE. 0 10 20 30 40 50 60 SNR [dB] -50 -40 -30 -20 -10 0 10 NMSE [dB] PROPOSED BCA+Postproc. Zero-Forzing (supervised) OPTIMAL NMSE (supervised) (b) Postprocessed proposal versus supervised techniques. Fig. 1. Averaged Normalized Mean Squared Error results over 100 Monte Carlo simulations of noisy and complex 10 ×10 random mixtures of communication sources (with a length of n= 300 samples) which are drawn with equiprobability from 32-APSK and 16-QAM modulations. Subfigure (a) favorably compares our BCA proposal with five state- of-the-art unsupervised techniques for the linear separation of complex signals. One can observe how the NMSE of the BCA proposal follows the optimal NMSE lower-bound, up to a small gap. Subfigure (b) reveals that, for moderate and high signal-to-noise ratios, the semi-blind postprocessing of the BCA proposal improves its performance, turning it comparable with the one of supervised methods that exploit the full knowledge of the sources. The supervised methods in the comparison are the zero-forzing solution (red dotted line) and the Wiener or optimal NMSE solution (black dotted line). 7. REFERENCES [1] Planck Collaboration Team, “Planck 2013 results. XII. Diffuse component separation,” Astronomy & Astrophysics, Vol. 571, n. A12, 2014. [2] S. Cruces, A. Cichocki, and S-i. Amari, “From blind signal extraction to blind instantaneous signal separation: criteria, algorithms and stability”, IEEE Transactions on Neural Networks, vol 15, no. 4, pp. 859–873, 2004. [3] C. He, X. Fei, Q. Cheng, H. Li, Z. Hu and Y. Tang, “A Survey of Community Detection in Complex Networks Using Nonnegative Matrix Factorization,” IEEE Transactions on Computational Social Systems, vol. 9, no. 2, pp. 440-457, 2022. [4] J. Eriksson, V. Koivunen, “Complex Random Vectors and ICA Models: Identifiability, Uniqueness, and Separability”, IEEE Transactions on Information Theory, vol. 52(3), 2006. [5] D. Lahat and C. Jutten, “Joint Independent Subspace Analysis: Uniqueness and Identifiability,” IEEE Transactions on Signal Processing, vol. 67, no. 3, pp. 684-699, 2019 [6] K. I. Diamantaras, “Blind Signal Processing Based on Data Geometric Properties,” in New Directions in Statistical Signal Processing: From Systems to Brain, S. Haykin, J. Principe, T. Sejnowski, and J. McWhirter (eds), MIT Press, 2006 [7] S. Cruces and I. Dur´ an, “The minimum support criterion for blind signal extraction: a limiting case of the strengthened Young’s inequality” proc. of the Int. Conference on ICA and BSS, Granada, Spain, pp. 57–64, 2004. [8] S. Cruces and A. Sarmiento, “Criterion for blind simultaneous extraction of signals with clear boundaries,” Electronics Letters, Vol. 41(21), pp. 1195–1196, 2005. [9] A. T. Erdogan, “A simple geometric blind source separation method for bounded magnitude sources,” IEEE Transactions on Signal Processing, vol. 54, no. 2, pp. 438–449, 2006. [10] F. Vrins, J. A. Lee and M. Verleysen, “A minimumrange approach to blind extraction of bounded sources” IEEE Transactions on Neural Networks, vol. 18, no. 3, pp. 809–822, 2007. [11] S. Cruces, I. Duran, A. Sarmiento, P. Aguilera, “Bounded component analysis of linear mixtures,” proc. of the IEEE Int. Conf. on Acoustics, Speech and Signal Proc. (ICASSP), pp. 1930–1943, 2010. [12] A. T. Erdogan, “A family of bounded component analysis algorithms,” proc. of the IEEE Int. Conf. on Acoustics, Speech and Signal Proc. (ICASSP), pp. 1881–1884, 2012. [13] S. Cruces, “Bounded component analysis of linear mixtures: A criterion of minimum convex perimeter”, IEEE Trans. on Signal Processing, Vol. 58(4), pp. 2141- 2154, 2010. [14] S. Cruces, “Bounded component analysis of noisy underdetermined and overdetermined mixtures.”, IEEE Trans. on Signal Processing, Vol. 26(5), pp. 964-981, 2015. [15] Bariscan Bozkurt, Alper T. Erdogan: “On Identifiable Polytope Characterization for Polytopic Matrix Factorization.”, IEEE Int. Conf. on Acoustics, Speech and Signal Proc. (ICASSP), pp. 3343-3347, 2022. [16] S. Cruces, I. Dur´ an, “The minimum risk principle that underlies the criteria of bounded component analysis”, IEEE Trans. on Neural Networks and Learning Systems, Vol. 26 (5), pp. 964-981, 2015. [17] A. T. Erdogan, “An information maximization based blind source separation approach for dependent and independent sources,” proc. of the IEEE Int. Conf. on Acoustics, Speech and Signal Proc. (ICASSP), pp. 4378–4382, 2022. [18] P. Ablin and J.-F. Cardoso and A. Gramfort, “Faster ICA Under Orthogonal Constraint” proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4464–4468, 2018. [19] R. Osserman, “The isoperimetric inequality” Bulleting of the Americal Mathematical Society, Vol. 84, No. 6, 1978. [20] J. F. Cardoso and A. Souloumiac, “Blind beamforming for non Gaussian signals”, IEE Proceedings-F, vol. 140, pp. 362–370, 1993. [21] A. J. van der Veen, “Asymptotic Properties of the Algebraic Constant Modulus Algorithm,” IEEE Transactions On Signal Processing, vol. 49(8), pp. 1796–1807, 2001. [22] M. Novey and T. Adali, “Complex ICA by Negentropy Maximization,” IEEE Journal on Neural Networks, vol. 19, pp. 596–609, 2008. [23] V. Zarzoso and P. Comon “Robust Independent Component Analysis by Iterative Maximization of the Kurtosis Contrast with Algebraic Optimal Step Size”, IEEE Transactions on Neural Networks, Vol. 21, No. 2, 2010, pp. 248-261.