Fast Convergence Algorithms for Coherence Optimization of Rank-1 Grassmannian Codebooks

456 F. AKRAM, ET AL., FAST CONVERGENCE ALGORITHMS FOR COHERENCE OPTIMIZATION OF RANK-1 .. . Fast Convergence Algorithms for Coherence Optimization of Rank-1 Grassmannian Codebooks Faisal AKRAM, Imran RASHID, Abdul GHAFOOR, Adil Masood SIDDIQUI Dept. of Electrical Engineering, College of Signals, National University of Science and Technology (NUST), Pakistan f[email protected], [email protected], [email protected], [email protected] Submitted July 6, 2018 / Accepted March 4, 2019 Abstract. Best Complex Antipodal Spherical Codes (BCASC) and Coherence Based Grassmannian Codebooks (CBGC) are state of the art algorithms to produce minimal coherence codebooks, however have high running time (relatively more in BCASC search than CBGC algorithm) which restricts their wider application. BCASC and CBGC algorithms are modified in a novel way by incorporating additional parameters adapted to three categories of codebook overcompleteness to check stagnance of optimization and divergent behaviour to achieve faster convergence. The proposed algorithms are compared with BCASC and CBGC algorithms to achieve similar coherence results in much less time. Keywords Grassmannian codebooks, hybrid metaheuristics, numerical optimization 1. Introduction A set of incoherent complex vectors forms a frame [1]. Compressed sensing uses a frame with low coherence amongst constituent vectors to achieve unique representation of sparse vectors with reliable recovery [2]. Such frames have numerous applications in signal processing, coding and communications [3]. A Grassmannian codebook is a set of vectors or matrices that span a corresponding Grassmannian manifold [4]. Difference sets are used to form Grassmannian codebooks analytically for certain configurations [5] and if analytical constructions are not possible then construction using numerical search method based on Lloyd’s algorithm are used [5]. Sloane et al. [6] performed extensive computations for modest dimensions to find optimal packings in Grassmannian spaces. Sequential smooth optimization based flexible technique is employed in [4] to construct Grassmannian codebooks. Gram matrix based optimization techniques include constructions using alternating projections in [7], [8] and iterative shrinkage with rank reduction in [9] and alternating minimization penalty method in [10]. In [11], existing codebooks with low coherence or near orthogonal systems are used to construct sensing matrices. The work in [12] uses additive and multiplicative characters of finite fields to construct similar sensing matrices. In [13], frames with low coherence are constructed using convex optimization whereas in [14], sequential iterative decorrelation by convex optimization is used and in [15] weighted least squares solved by shifted power is used. In [16], best spherical codes were formed and later in [17], best antipodal spherical codes with low coherence were formed in real domain. In [18], Best Complex Antipodal Spherical Codes (BCASC) are formed by a sequential procedure to optimize coherence, which aims at maximizing the Euclidean distance between complex vectors to reduce coherence. Antipodals of complex vectors are incorporated in the optimization process which increase the processing time. Adapted from [18], in [19], Coherence Based Grassmannian Codebook (CBGC) algorithm, aims to optimize coherence by directly reducing the coherence between complex vectors. The codebooks are produced with similar coherence values to [18] but with reduction in processing time owing to optimization without incorporating antipodals of complex vectors. It is pertinent to mention that both BCASC and CBGC algorithms differ in goal function and the way in which they converge respectively. It is also worth mentioning that the CBGC algorithm which is an adaptation of BCASC algorithm doesn’t always guarantee reduction in time as compared to BCASC algorithm. Moreover, BCASC algorithm has also been shown to achieve dictionary adaptation of sensing matrix [20] whereas the same for CBGC algorithm is to be attempted. Alternatively, the optimizationisperformed usingmetaheuristic algorithms which are adapted for particular problems to achieve desired solution quality in reduced computing time [21]. Metaheuristics (include genetic/evolutionary algorithms, tabu search, simulated annealing, particle swarm optimization, ant colony optimization) do not exert additional demands on an optimization problem and are flexible in adapting to the specifics of a problem to achieve better performance [21]. DOI: 10.13164/re.2019.0456 SIGNALS RADIOENGINEERING, VOL. 28, NO. 2, JUNE 2019 457 Hybrid metaheuristics synergistically combine various optimization strategies (a combination of two metaheuristic or of an exact and metaheuristic algorithm) to achieve an optimum solution to the problem in a reduced amount of time [22]. Some hybrid metaheuristic schemes include [23–28]. In [23], vector quantization codebooks are generated using efficient and fast converging particle swarm optimization. In [24], the accelerated converging ant colony optimization process is used for vector quantization codebooks generation. In [25], fish school search algorithm based on swarm clustering algorithm is used for vector quantization codebook generation providing PSNR gains in comparison to the swarm clustering algorithm. In [26], codebooks for power control in distributed relay beamforming network are generated using Lloyd’s algorithm and a metaheuristic general search algorithm. In [27], joint precoding and antenna selection is done in multiple-input multiple-output environment while using cross-entropy [28] method to maximize channel capacity. In this work, BCASC and CBGC algorithms are analyzed and modified to produce rank-1 Grassmannian codebooks by tuning existing parameters and incorporating additional metaheuristics adapted to categories of codebook overcompleteness which reduce running time without compromising coherence. 2. Preliminaries 2.1 Coherence Bounds Consider a matrix A∈ CM×Nwhere M<N, its coherence is defined as µ(A)=maxi,j | hai,aji | kaik kajk, where aidenotes the ith column of matrix A[18]. Lower bounds on achievable coherences for complex matrices [29–37], with their respective configurations (Category I, Category II, Category III) is: µbd(A)=                             qN−M M(N−1),if N≤M2[Category I] maxq1 M,q2N−M2−M (M+1)(N−M),1−2N−1 M−1, if M2<N≤2(M2−1)[Category II] maxq2N−M2−M (M+1)(N−M),1−2N−1 M−1, if 2(M2−1)<N[Category III]. (1) 2.2 BCASC Search Algorithm BCASC algorithm [18], performs sequential Lagrange based optimization on an initial random matrix Aand maximizes the minimum Euclidean distance between any two vectors of the matrix. Optimization function for low coherence matrices is given as: g(A, λ)= N Õ n=1Õ n,l kan−alk−(p−2)+ N Õ n=1 λn(kank2−1)(2) where λ={λn}N n=1are the Lagrange multipliers with unit radius constraint of spherical codes and p∈ {21,22. . . , 29} is the free parameter. The sequential optimization process alters the location of points formed by initial random unit norm complex vectors on unit norm sphere under the mutual force of repulsion due to similar charge particles being assumed to be in place at the respective points. The force vector is derived by finding the necessary conditions for a global minimum in (2): fn←∫2π κ=0Õ l,n an−aleiκ kan−aleiκkpdκ!N n=1 (3) where underlining represents unit normalization. BCASC algorithm involves infinite antipodals of each vector in each iteration. Force vector calculated using K-points approximation fn← K Õ k=1Õ l,n an−alei2πk K kan−alei2πk Kkp!N n=1 ,(4) reduces running time at the cost of slight coherence deviation [18]. After dampened application of the forces, the matrix is updated as: A(k)=A(k−1)+αF(k), where dampening factor αis related to free parameter pand causes coarse to fine adjustments. Optimization process doesn’t progress to next value of p, until force vectors converge to codewords kf(k) n−a(k) nk<10−10. 2.3 CBGC Algorithm Adapted from BCASC algorithm [18], CBGC algorithm [19] directly optimizes the coherence of the random complex vectors set. It performs Lagrange based optimization of the objective function, g(A, λ)=Õ n,l|han,ali|2−β2µ2 bdp + N Õ n=1 λn(kank2−1)(5) where β=0.5improves stability. The force vector is derived by finding the equilibrium conditions for (5) as: f(k) n=−2Õ n,l|ha(k) n.a(k) li|2−β2µ2 bdp−1 ha(k) l,a(k) ni.a(k) l(6) where a(k) lrepresents unit norm vector at index lin kth iteration. After dampened application of the forces the matrix is updated. Optimization process moves to the next value of p, once condition ka(k) n−a(k−1) nk<10−10 is met. 458 F. AKRAM, ET AL., FAST CONVERGENCE ALGORITHMS FOR COHERENCE OPTIMIZATION OF RANK-1 .. . 3. Proposed Algorithms 3.1 Discussion on BCASC Algorithm BCASC algorithm (adapted from [17]) is a sequential coherence optimization process based on complex vector relocations under the influence of a resultant force vector (calculated using numerical integration involving infinite antipodals (3)). Numerical integration increases complexity and processing time. K-point summation approximation based force vector calculation reduces processing time with coherence values deviation [18]. The algorithm convergence largely depends upon the quality of the initial random seed (orientation of the random complex vectors) and the level of over-completeness of the desired matrix configuration. Moreover, the convergence criteria of fixed point found i.e., kfn−ank<10−10 is checked in each iteration. Fixed point found criteria aims at converging the force vectors to codewords and thereby attaining an equilibrium. During the course of algorithm progression, the matrix vectors at times reach a situation where force vectors based updation of the complex matrix causes back and forth setting of vectors without significantly changing the orientation until next value of free parameter ptakes effect. Such optimization stagnance wastes computation time. Furthermore, runtime coherence monitoring during the optimization process reveals a deteriorating coherence behaviour. The existing stopping criterion mostly doesn’t stop at a point where worst case coherence is found to be at a desirable value. 3.2 Fast BCASC Algorithm (FBCASC) BCASC algorithm does achieve its optimization goal but the algorithm progression highlights room for improvement in the convergence rate without compromising the quality of resultant matrix. The proposed FBCASC algorithm aims at modifying the K-point summation BCASC algorithm with the ability to terminate an interim optimization sub-problem once no significant improvement (stagnance in optimization) or worsening of goal function (divergence of optimization) occurs to allow reduction in overall computational time without deteriorating coherence achieved. It includes tuning of the existing parameters and introduction of a metaheuristics layer atop the existing algorithm in accordance with the codebook category to counter stagnance and divergence issues. FBCASC algorithm incorporates codebook category wise adaptive tuned parameters and metaheuristics (Algorithm 1, Line 5) to allow even finer reductions in time without compromising coherence. Stagnance in coherence is assessed by monitoring interiteration coherence deviation compared with a pre-defined tolerance. The coherence of the interim-matrix is calculated after every 100 iterations and is denoted as µ(g). The optimization process is found to be stagnant if condition |µ(g)−µ(g−1)|<µstol is satisfied where µstol is the stagnance coherence tolerance (Algorithm 1, Line 20) and pre-defined metaheuristic stagnant coherent count θ(initiated to θopt for a particular value of p) is decremented by a unit (Algorithm 1, Line 21). Once the stagnant coherence count θbecomes zero, the optimization sub-problem is made to exit for the specific value of free parameter p. Divergence of coherence is checked by decrementing the pre-defined metaheuristic divergence tolerance ξ(initiated to ξopt for a particular value of p) by a unit, if coherence value increases from the last observed coherence i.e., µ(g)> µ(g−1)(Algorithm 1, Line 26–27). The optimization sub-problem proceeds to the next value of free parameter p once ξ=0. The optimization process is stopped at the iteration where the condition |µ(g)−µbd(A)| <10−6is satisfied (Algorithm 1, Line 23–24) and the interim matrix is given as output. 3.3 Adapted Parameter Selection for FBCASC Algorithm In order to get low coherence matrices in as less time as possible for a given configuration, the parameters error threshold ε, summation points Kare tuned and optimum values for metaheuristic stagnant coherence tolerance µstol, stagnant coherence count θand divergence tolerance ξare adapted for each of three categories of codebooks (1). Algorithm 1 FBCASC 1: A∈CM×N.Random seed 2: αinit ←0.9, α ←αinit .Dampening factor 3: imax ←105,pmax ←210,p←2.Max iterations and free parameter 4: η←0, µbd(A).Coherence bound met and bound for A∈CM×N(1) 5: Adaptive settings for configurations CM×N Category I Category II Category III Description ε=10−4ε=10−5ε=10−5.Error threshold K←13 K←18 K←50 .Summation approx. points µstol ←10−2µstol ←10−2µstol ←10−5.Stagnant coherence tolerance θopt ←1θopt ←4θopt ←12 .Stagnant coherence count ξopt ←3ξopt ←6ξopt ←5.Divergence tolerance 6: while p<pmax &η=0do 7: γ←0,.Fixed-point found 8: ξ←ξopt, θ ←θopt,.Initialize optimum parameters 9: i=1,g=1,µ(g)←0,.Indices and coherence initiation 10: while i≤imax &γ=0&η=0&θ,0&ξ,0do 11: for k=1to Ndo 12: fn←ÍK k=1Íl,n an−alei2πk K kan−alei2πk Kkp .Calculate forces (4) 13: end for 14: {an}N n=1← {an+αfn}N k=1.Normalized force application 15: if all kfk−akk< ε then 16: γ←1.Fixed point found 17: end if 18: if mod (i,100)=0then 19: µ(g)=arg maxr,t |har,ati| karkkatk.Coherence calculation 20: if |µ(g)−µ(g−1)|< µstol then 21: θ=θ−1.Reduce stagnant coherence count 22: end if 23: if |µ(g)−µbd(A)| <10−6then 24: η←1.Coherence bound met 25: end if 26: if µ(g)> µ(g−1)then 27: ξ=ξ−1.Reduce divergence tolerance 28: end if 29: g=g+1 30: end if 31: i=i+1 32: end while 33: p←2p,α←αinit (p−1).Adjust free parameter and dampening factor 34: end while RADIOENGINEERING, VOL. 28, NO. 2, JUNE 2019 459 10-110-210-310-410-510-610-710-810-9 10-10 0 5 10 15  Run-time (a) 8 10 13 16 18 20 22 24 26 28 30 50100 K summation points (b) 10-110-210-310-410-510-610-710-810-9 10-10 µst ol (c) 12 3 4 5 6 7 8 9 10111213141516 θ (d) 10-3 10-4 10-5 10-6 10-7 10-8 10-9 10-10 0.3535 0.3537 0.3539 0.3541  Coherence (e) 8 10 13 16 18 20 22 24 26 28 30 50100 K summation points (f) 10-110-210-310-410-510-610-710-810-9 10-10 µst ol (g) 12 3 4 5 6 7 8 9 10111213141516 θ (h) 1234 5 6 7 8 9 10 1 2 3 4 ξ Runtime (i) 1234 5 6 7 8 9 10 0.3535 0.3537 0.3539 0.3541 ξ Coherence (j) Fig. 1. FBCASC adaptive parameters selection for (4,7) using box plots (box encapsulates 25th to 75th percentile, central mark indicates median, whiskers extend to extreme data points and outliers are plotted using the ’+’ symbol): (a) and (e) K=15,µstol =10−2,ξ=5,θ=2, (b) and (f) ε=10−4,µstol =10−2,ξ=5,θ=2, (c) and (g) ε=10−4,K=13,ξ=5,θ=2, (d) and (h) ε=10−4,K=13,µstol =10−2, ξ=5, (i) and (j) ε=10−4,K=13,µstol =10−2,θ=1. 10-110-210-310-410-510-610-710-810-9 10-10 0 5 10 15  Run-time (a) 10-110-210-310-410-510-610-710-810-9 10-10 0 5 10 µst ol (b) 400 1200 2000 2800 3600 4400 5200 6000 6800 7600 0 5 10 θ (c) 50 100 150 200 250 300 350 400 450 500 550 600 650 700 750 800 850 900 950 1000 0 5 10 ξ (d) 10-110-210-310-410-510-610-710-810-9 10-10 0.3500 0.4500 0.5500 0.6500 0.7500  Coherence (e) 10-110-210-310-410-510-610-710-810-9 10-10 0.3334 0.3335 0.3336 µst ol (f) 400 1200 2000 2800 3600 4400 5200 6000 6800 7600 0.3334 0.3335 θ (g) 50 100 150 200 250 300 350 400 450 500 550 600 650 700 750 800 850 900 950 1000 0.3334 0.3335 ξ (h) Fig. 2. FCBGC adaptive parameters selection for (5,10)using box plots (box encapsulates 25th to 75th percentile, central mark indicates median, whiskers extend to extreme data points and outliers are plotted using the ’+’ symbol): (a) and (e) µstol =10−4,ξ=100,θ=6000, (b) and (f) ε=10−6,ξ=100,θ=6000, (c) and (g) ε=10−6,µstol =10−4,ξ=100, (d) and (h) ε=10−6,µstol =10−4,θ=6000. 460 F. AKRAM, ET AL., FAST CONVERGENCE ALGORITHMS FOR COHERENCE OPTIMIZATION OF RANK-1 .. . Selection of tuned parameters and the metaheuristics for each category is done by considering one model configuration for each category to generalize. The step by step process looks for a suitable value to one existing parameter or a metaheuristic at a time while keeping other parameters constant at a preferable value or the one already found to be appropriate. The procedure assumes that the parameters and the metaheuristics are independent due to their respective nature. In Fig. 1(a) box plots of run-time variation and in Fig. 1(f) box plots of coherence deviation for varying εerror threshold while keeping other parameters constant for ten test trials for FBCASC algorithm configuration (4,7)are shown. An appropriate value of parameter is chosen while giving equal weight to the lowest coherence achieved and low running time with minimal deviation. Suitable tuned value of ε=10−4is chosen on the basis of low run-time as well as minimal deviation coupled with low coherence and low deviation. The remaining of Fig. 1 shows process of finding suitable tuned value for summation points Kand optimum values for metaheuristic stagnant coherence tolerance µstol, stagnant coherence count θand divergence tolerance ξusing box plots for coherence and runtime variation for ten test trials for FBCASC algorithm configuration (4,7). Similar process is adopted to find suitable parameters for category II and III configurations (summary given in Algorithm 1 Line 5). 3.4 Discussion on CBGC Algorithm CBGC algorithm [19] (an adaptation of BCASC algorithm), performs faster than BCASC algorithm due to absence of antipodals. CBGC algorithm convergence criteria i.e, kak n−ak−1 nk ≤ 10−10 checks equilibrium being achieved but it doesn’t check unnecessary increase in optimization time. Moreover, monitoring of coherence for interim matrix at each iteration has shown that at times the optimization process on one hand doesn’t fulfil the convergence criteria and on the other doesn’t progress towards the attainment of optimization goal due to overtly stringent convergence constraint. Worsening of the optimization process is also observed where coherence tends to increase or diverge. At times, even though the lowest possible coherence is attained with a desirable resolution but stopping criterion does not allow the process to halt. 3.5 Fast CBGC (FCBGC) CBGC algorithm is broadly successful in its optimization goal but the algorithm progression higlights the need for improvement in the overall convergence rate. In the proposed FCBGC (Algorithm 2, a modification of CBGC), the existing parameters are tuned and a layer of metaheuristics is defined over the algorithm to overcome the issues of stagnant and divergent optimization. Stagnant coherence is overcome by incorporatingmetaheuristicstagnantcoherencetoleranceand its respective count. Divergence of coherence is countered by using metaheuristic divergence tolerance decrement. Owing to better convergence of CBGC, compared to BCASC, the additional constraints are made functional in every iteration. Coherence is calculated at every iteration (Algorithm 2, Line 12) denoted as µ(i)for the ith iteration. Stagnant coherence is checked using |µ(i)−µ(i−1)|< µstol where µstol is the stagnant coherence tolerance, if found true then stagnance coherence count θ(initiated to θopt for a particular value of p) is decremented by a unit (Algorithm 2, Line 13–14). Once the stagnant coherence tolerance θbecomes 0, the optimization process progresses to the next value of p. Coherence divergence is checked by decrementing divergence tolerance ξ(initiated to ξopt for a particular value of p) by a unit, provided the condition µ(i)>µ(i−1)holds true (Algorithm 2, Line 19–20).When the divergence tolerance ξ becomes 0, the optimization process progresses to the next value of p. When (|µ(k)−µbd(A)| <10−6), the optimization process is stopped and the interim-matrix is given as output (Algorithm 2, Line 16–17). Algorithm 2 FCBGC 1: A∈CM×N.Random seed 2: αinit ←0.04,α←αinit .Dampening factor 3: imax ←105,pmax ←29,p←2.Max iterations, free parameter 4: η←0, µbd(A).Coherence bound met and bound for A∈CM×N(1) 5: Adaptive settings for configurations CM×N Category I Category II Category III Description ε=10−6ε=10−8ε=10−8.Error threshold µstol ←10−4µstol ←10−4µstol ←10−5.Stagnant coherence tolerance θopt ←6000 θopt ←5200 θopt ←6000 .Stagnant coherence count ξopt ←450 ξopt ←650 ξopt ←100 .Divergence tolerance 6: while p≤pmax &η=0,do 7: i=1, µ(0)←1,.Initialize index and coherence 8: ξ←ξopt, θ ←θopt,.Initialize optimum parameters 9: while i≤imax & any ka(i) n−a(i−1) nk ≥ ε&θ,0&ξ,0&η=0do 10: Calculate F(i)=[f(i) 1f(i) 2. . . f(i) N].Force calculation (6) 11: A(i)=A(i−1)+αF(i).Update and normalize A 12: µ(i)=arg maxr,t |har,ati| karkkatk.Interim coherence calculation 13: if |µ(i)−µ(i−1)|< µstol then 14: θ=θ−1.Reduce stagnant coherence count 15: end if 16: if |µ(i)−µbd(A)| <10−6then 17: η←1.Coherence bound met 18: end if 19: if µ(i)> µ(i−1)then 20: ξ=ξ−1.Reduce divergence tolerance 21: end if 22: i=i+1.Increase iteration 23: end while 24: p←2p,α←αinit (p−1).Adjust free parameter and dampening factor 25: end while 3.6 Adapted Parameter Selection for FCBGC Algorithm The adapted parameters for FCBGC algorithm are selected through a method similar to the one adopted for FBCASC algorithm (as discussed in Sec. 3.3). In Fig. 2(a) box plots of run-time variation and in Fig. 2(e) box plots of coherence deviation for varying εerror threshold while keeping other parameters constant for ten test trials for FCBGC algorithm configuration (5,10)are shown. Suitable tuned value of ε=10−6is chosen on the basis of low run-time as well as minimal deviation coupled with low coherence and low deviation. The remaining of Fig. 2 shows process of RADIOENGINEERING, VOL. 28, NO. 2, JUNE 2019 461 finding suitable values for metaheuristic stagnant coherence tolerance µstol, stagnant coherence count θand divergence tolerance ξusing box plots for coherence and runtime variation for ten test trials for FCBGC algorithm configuration (5,10). Similar process is adopted to find suitable tuned parameters and metaheuristics for category II and III configurations (summary given in Algorithm 2 Line 2). 4. Numerical Results The algorithms are implemented in Matlab R2017a, and the machine used has Intel Core i7-6700 CPU @ 3.40 GHz octa-core 64-bit processor with 32 GB RAM. Minimum and maximum coherences achieved and running times required in ten test runs are compared for BCASC, FBCASC, CBGC and FCBGC algorithms in Tab. 1. BCASC algorithm is implemented using K=100 summation approximation points for producing the results of all configurations considered. The adaptive settings of parameters (FBCASC Algorithm 1 Line 5 and FCBGC Algorithm 2 Line 5) as per the category of the configuration considered are used to produce the codebooks. The results generated are not simulation invariant due to deterministic optimization and variety of random seeds. Significant reduction in runtimes with comparable coherences are achieved using FBCASC and FCBGC algorithms respectively. In Fig. 3, coherence achieved at each iteration versus number of iterations is plotted for category II configuration (4,20). Although the amount of processing involved in each iteration significantly differs in BCASC and CBGC algorithms and their subsequent modifications, yet in Fig. 3, the coherence optimization profile shows relative trend of convergence for BCASC, FBCASC, CBGC and FCBGC algorithms. In FBCASC and FCBGC algorithms, the stagnant behaviour and divergence is avoided. Significant drop in number of iterations required to achieve similar coherence results in FBCASC and FCBGC algorithms also reduces the processing time. Gram-matrix (AHA) off-diagonal values distribution for BCASC algorithm, FBCASC algorithm and for |FBCASCBCASC|for A∈C4×64 are shown in Fig. 4(a), (c) and (e) respectively. Similarly, in Fig. 4(b), (d) and (e), the distributionof Gram-matrix (AHA)off-diagonal valuesfor A∈C4×64 for CBGC algorithm, FCBGC algorithm and for |FCBGCCBGC|are shown. In Fig. 4 (e) and (f), it is observed that the absolute difference distributions of off-diagonal values for the proposed algorithms and principle algorithms shows minimal variation. This highlights that the matrices generated by the proposed algorithms are similar in quality to the ones generated by the principle algorithms. Extensive experimentation reveals that some configurations of category I ((2,4),(4,16),(5,25),(6,36)) yield offdiagonal coherence distribution with the variation of ≤0.01 (See Fig. 5). However, for the configuration (3,9)the variation is ≤0.02. This also confirms the existence of tight frames for the said configurations as given in [7]. 0 10000 20000 30000 40000 50000 0.5 0.55 0.6 Iterations Coherence CBGC FCBGC BCASC FBCASC Fig. 3. Coherence optimization profile for (4,20)configuration. 0 0.2 0.40.60.8 101 102 103 Off-diagonal values Frequency a: BCASC 0 0.2 0.40.60.8 101 102 103 Off-diagonal values Frequency b: CBGC 0 0.2 0.40.60.8 101 102 103 Off-diagonal values Frequency c: FBCASC 0 0.2 0.40.60.8 101 102 103 Off-diagonal values Frequency d: FCBGC 0 0.2 0.40.60.8 101 102 103 Off-diagonal values Frequency e: |FBCASC-BCASC| 0 0.2 0.40.60.8 101 102 103 Off-diagonal values Frequency f: |FCBGC-CBGC| Fig. 4. Off-diagonal values distribution for (4,64)configuration. 0.35 0.4 0.45 0.5 0.55 0.6 101 102 103 Coherence Frequency (6,36) (5,25) (2,4) (4,16) (3,9) Fig. 5. Combined coherence distribution for N=M2. 5. Conclusion FBCASC and FCBGC algorithms are proposed to address the issue of processing time in BCASC and CBGC algorithms. Comprehensive comparison of proposed algorithms with the existing algorithms is given for numerous configurations from different categories of overcomplete complex matrices. The proposed algorithms using category-wise adaptive parameters significantly reduce the running time without deteriorating the coherence values. 462 F. AKRAM, ET AL., FAST CONVERGENCE ALGORITHMS FOR COHERENCE OPTIMIZATION OF RANK-1 .. . Coherence Runtime (seconds) Minimum Maximum Minimum Maximum Category M N µbd [18] BCASC FBCASC CBGC FCBGC BCASC FBCASC CBGC FCBGC BCASC FBCASC CBGC FCBGC BCASC FBCASC CBGC FCBGC I 4 5 0.2500 0.2500 0.2500 0.2500 0.2500 0.2500 0.2500 0.2500 0.2500 0.28 0.07 0.02 0.005 0.45 0.16 0.08 0.014 4 7 0.3535 0.3535 0.3535 0.3535 0.3535 0.3536 0.3536 0.3535 0.3535 9.92 0.56 0.18 0.07 532.07 0.95 0.29 0.138 4 16 0.4472 0.4472 0.4472 0.4472 0.4472 0.4472 0.4472 0.4472 0.4472 169.75 3.66 0.70 0.26 2335.6 5.00 1.29 1.21 5 10 0.3333 0.3333 0.3333 0.3333 0.3333 0.3334 0.3337 0.3334 0.3334 20.07 2.30 0.54 0.23 270.05 13.27 128.23 6.23 5 16 0.3830 0.3889 0.3888 0.3889 0.3889 0.3906 0.3925 0.3903 0.3899 351.61 38.57 96.17 5.45 2169.24 61.23 240.08 15.11 7 42 0.3492 0.3559 0.3544 0.3541 0.3541 0.3752 0.3828 0.3750 0.3806 16716.42 121.33 64.27 16.79 32145 438.14 637 85.45 II 2 6 0.7071 0.7071 0.7071 0.7071 0.7071 0.7076 0.7071 0.7071 0.7071 181.19 0.05 0.19 0.13 323.56 0.08 1.85 0.583 3 16 0.6202 0.6491 0.6487 0.6491 0.6487 0.6491 0.6518 0.6491 0.6506 2118.96 22.32 145.82 10.61 23971 24.11 227.10 25.26 4 20 0.5000 0.5000 0.5000 0.5004 0.5000 0.5284 0.5182 0.5290 0.5350 254.76 7.14 49.23 1.687 3226.40 17.39 310.28 39.51 5 30 0.4472 0.4472 0.4472 0.4472 0.4472 0.4472 0.4480 0.4472 0.4475 617.83 35.66 72.15 5.74 3638.57 71.54 151.45 46.84 6 37 0.4082 0.4141 0.4082 0.4140 0.4082 0.4148 0.4150 0.4154 0.4176 4699.90 93.30 425.65 38.62 25347 148.87 939.96 91.29 12 60 0.2603 0.2749 0.2743 0.2736 0.2734 0.2759 0.2762 0.2738 0.2753 34168 1032.10 2934.66 84.69 197600 1105.40 3271.66 190.91 III 2 7 0.7302 0.7786 0.7786 0.7995 0.7782 0.7790 0.7789 0.8090 0.8089 339.17 3.46 0.62 0.512 767.2 4.18 1.53 1.47 2 8 0.7500 0.7950 0.7941 0.7942 0.7942 0.7950 0.7952 0.7942 0.7942 493.70 4.83 3.15 0.679 4598.2 7.00 4.52 1.377 3 18 0.6324 0.6637 0.6635 0.6635 0.6635 0.6638 0.6889 0.6830 0.6659 330.81 40.98 14.72 11.52 8735.7 53.59 124.43 24.16 3 20 0.6416 0.6877 0.6871 0.6872 0.6872 0.6901 0.6873 0.6892 0.6903 3174.5 81.18 199.70 16.46 4470.3 114.06 432.24 32.12 4 32 0.5606 0.5783 0.5781 0.5777 0.5777 0.5785 0.5788 0.5781 0.5790 1084.94 281.20 25.29 12.22 21072.3 419.29 521.58 58.01 4 64 0.6000 0.6877 0.6877 0.6875 0.6882 0.6878 0.6889 0.6883 0.6925 11523.6 77.15 2256.95 107.79 48528.2 116.09 2429.05 178.52 Tab. 1. Minimum and maximum coherence and runtimes in ten test trials for BCASC, FBCASC, CBGC and FCBGC. References [1] CHRISTENSEN, O. An Introduction to Frames and Riesz Bases. Birkhauser, 2016, ISBN: 978-0-8176-8224-8 [2] CANDES, E. J., WAKIN, M. B. An introduction to compressive sampling. IEEE Signal Processing Magazine, 2008, vol. 25, no. 2, p. 21–30. DOI: 10.1109/MSP.2007.914731 [3] LOVE, D., HEATH, R.W., STROHMER, T. Grassmannian beamforming for multiple input multiple output wireless systems. IEEE Transactions on Information Theory, 2003, vol. 49, no. 10, p. 2735–2747. DOI: 10.1109/TIT.2003.817466 [4] MEDRA, A., DAVIDSON, T. N. Flexible codebook design for limited feedback systems via sequential smooth optimization on the Grassmannian manifold. IEEE Transactions on Signal Processing, 2014, vol. 62, no. 5, p. 1305–1318. DOI: 10.1109/TSP.2014.2301137 [5] XIA, P., ZHOU, S., GIANNAKIS, G.B. Achieving the Welch bound with difference sets. IEEE Transactions on Information Theory, 2005, vol. 51, no. 5, p. 1900– 1907. DOI: 10.1109/TIT.2005.846411 [6] CONWAY, J. H., HARDIN, R. H., SLOANE, N. J. Packing lines, planes, etc.: Packings in Grassmannian spaces. Experimental Mathematics, 1996, vol. 5, no. 2, p. 139–159. DOI: 10.1080/10586458.1996.10504585 [7] TROPP, J., DHILLON, I. S., HEATH, R. W., et al. Designing structured tight frames via an alternating projection method. IEEE Transactions on Information Theory, 2005, vol. 51, no. 1, p. 188–209. DOI: 10.1109/TIT.2004.839492 [8] DHILLON, I. S., HEATH, R. W., STROHMER, T., et al. Constructing packings in Grassmannian manifolds via alternating projection. Experimental Mathematics, 2008, vol. 17, no. 1, p. 9–35. DOI: 10.1080/10586458.2008.10129018 [9] ELAD, M. Optimized projections for compressed sensing. IEEE Transactions on Signal Processing, 2007, vol. 55, no. 12, p. 5695–5702. DOI: 10.1109/TSP.2007.900760 [10] SADEGHI, M., BABARIE-ZADEH, M. Incoherent unit-norm frame design via an alternating minimization penalty method. IEEE Signal Processing Letters, 2017, vol. 24, no. 1, p. 32–36. DOI: 10.1109/LSP.2016.2632199 [11] LI, S., GE, G. Deterministic sensing matrices arising from near orthogonal systems. IEEE Transactions on Information Theory, 2014, vol. 60, no. 4, p. 2291–2302. DOI: 10.1109/TIT.2014.2303973 [12] TAN, P., ZHOU, Z., ZHANG, D. A construction of codebooks nearly achieving the Levenstein bound. IEEE Signal Processing Letters, 2016, vol. 23, no. 10, p. 1306–1309. DOI: 10.1109/LSP.2016.2595106 [13] RUSU, C. Design of incoherent frames via convex optimization. IEEE Signal Processing Letters, 2013, vol. 20, no. 7, p. 673–676. DOI: 10.1109/LSP.2013.2263280 [14] RUSU, C., GONZALEZ-PRELCIC, N. Designing incoherent frames through convex techniques for optimized compressed sensing. IEEE Transactions on Signal Processing, 2016, vol. 64, no. 9, p. 2334– 2344. DOI: 10.1109/TSP.2016.2521607 [15] DUMITRESCU, B. Designing incoherent frames with only matrixvector multiplications. IEEE Signal Processing Letters, 2017, vol. 24, no. 9, p. 1265–1269. DOI: 10.1109/LSP.2017.2723044 [16] LAZIC, D.E. Class of block codes for the gaussian channel. Electronic Letters, 1980, vol. 16, no. 5, p. 185–186. DOI: 10.1049/el:19800133 [17] LAZIC, D. E., ZÖRLEIN, H., BOSSERT, M. Low coherence sensing matrices based on best spherical codes. In Proceedings of 9th International ITG Conference on Systems, Communication and Coding (SCC). Munich (Germany), 2013. ISBN: 978-3-8007-3482-5 [18] ZÖRLEIN, H., BOSSERT, M. Coherence optimization and best complex antipodal spherical codes. IEEE Transactions on Signal Processing, 2015, vol. 63, no. 24, p. 6606–6615. DOI: 10.1109/TSP.2015.2477052 [19] LAUE, H.E.A., DU PLESSIS, W. P. A coherence-based algorithm for optimizing rank-1 Grassmannian codebooks. IEEE Signal Processing Letters, 2017, vol. 24, no. 6, p. 823–827. DOI: 10.1109/LSP.2017.2690466 [20] ZÖRLEIN, H. Channel Coding Inspired Contributions to Compressed Sensing. Ph.D. dissertation, Universitat Ulm. 2015. DOI: 10.18725/OPARU-3247 [21] GLOVER, F., SÖRENSEN, K. Metaheuristics. Scholarpedia, 2015, vol. 10, no. 4. DOI:10.4249/scholarpedia.6532 [22] BLUM, C., PUCHINGER, J., RAIDL, G. R., ROLI, A. Hybrid metaheuristics in combinatorial optimization: A survey. Applied Soft Computing, 2011, vol. 11, no. 6, p. 4135–4151. DOI: 10.1007/978-3-540-78295-7_8 RADIOENGINEERING, VOL. 28, NO. 2, JUNE 2019 463 [23] TSAI, C., LIN, C., CHIANG, M. et al. A time-efficient particle swarm optimization-based codebook generation algorithm. In Proceedings of the IEEE Congress on Evolutionary Computation. Barcelona (Spain), 2010, p. 1–6. DOI: 10.1109/CEC.2010.5585985 [24] TSAI, C., TSENG, S., YANG, C., et al. PREACO: A fast ant colony optimization for codebook generation. Applied Soft Computing, 2013, vol. 13, no. 6, p. 3008–3020. DOI:10.1016/j.asoc.2013.01.017 [25] FONSECA, C. S., FERREIRA, F.A.B.S., MADEIRO, F. Vector quantization codebook design based on Fish School Search algorithm. Applied Soft Computing, 2018, vol. 73, p. 958–968. DOI: 10.1016/j.asoc.2018.09.025 [26] ZHENG, M., DONG, M. On codebook design for distributed relay beamforming network. In Proceedings of the IEEE International Conference on Communications in China (ICCC). Beijing (China), 2012, p. 323–328. DOI:10.1109/ICCChina.2012.6356901 [27] CHEN, J., CHIU, M., YANG, Y., et al. Efficient capacity-based joint quantized precoding and transmit antenna selection using crossentropy method for multiuser MIMO systems. International Journal of Antennas and Propagation, 2012, vol. 2012, Article ID 965834, 7p. DOI 10.1155/2012/965834 [28] RUBINSTEIN, R. The Cross-Entropy Method for Combinatorial and Continuous Optimization. Methodology and Computing in Applied Probability, 1999, vol. 7, no. 1, p. 127–190. DOI:10.1023/A:1010091220143 [29] WELCH, L. Lower bounds on the maximum cross correlation of signals. IEEE Transaction on Information Theory, 1974, vol. 20, no. 3, p. 397–399. DOI: 10.1109/TIT.1974.1055219 [30] SARWATE, D. V. Meeting the Welch Bound with Equality. Chapter in Ding, C., Helleseth, T., Niederreiter, H. Sequences and their Applications. Eds. Berlin, Germany: Springer-Verlag, 1999 ISBN: 978-1-4471-0551-0 [31] DELSARTE, P., GOETHALS, J. M., SEIDEL, J. J. Bounds for systems of lines and Jacobi polynomials. Philips Research Reports, 1974, vol. 30, no. 3, p. 91–105. Available at: http://www.extra.research.philips.com/hera/people/aarts/_Philips Bound Archive/PRRep/PRRep-30-1975B-091.pdf [32] HENKEL, O. Sphere-packing bounds in the Grassmann and Stiefel manifolds. IEEE Transactions on Information Theory, 2005, vol. 51, no. 10, p. 3445–3456. DOI: 10.1109/TIT.2005.855594 [33] PITAVAL, R.A., TIRKKONEN, O., BLOSTEIN, S. Low complexity MIMO precoding codebooks from orthoplex packings. In Proceedings of the IEEE International Conference on Communication (ICC). Kyoto (Japan), 2011, p. 1–5. DOI: 10.1109/icc.2011.5963214 [34] LEVENSHTEIN, V. I., KABATIANSKY, G. A. On bounds for packings on a sphere and in space. Problemy Peredachi Informatsii, 1978, vol. 14, no. 1, p. 3–25. [35] LEVENSHTEIN,V. I.Bounds forpackingsof metric spacesand some of their applications. Problemy Kibernetiki, 1983, vol. 40, p. 43–110. [36] DING, C., YIN, J. Signal sets from functions with optimum nonlinearity. IEEE Transactions on Communication, 2007, vol. 55, no. 5, p. 936–940. DOI: 10.1109/TCOMM.2007.894113 [37] MUKKAVILLI, K., SABHARWAL, A., ERKIP, E., et al. On beamforming with finite rate feedback in multiple-antenna systems. IEEE Transactions on Information Theory, 2003, vol. 49, no. 10, p. 2562–2579. DOI: 10.1109/TIT.2003.817433 About the Authors . . . Faisal AKRAM received his bachelors degree in Telecommunication Engineering from National University of Science and Technology (NUST), Pakistan, in 2005, the masters degree in Communication Technology from University of Ulm, Germany, in 2013. He is currently a Ph.D. candidate at the NUST, Pakistan. His research interests include compressed sensing, wireless communication, mm-wave hybrid MIMO systems and channel coding. Imran RASHID received the B.E. degree in Electrical (Telecomm) Engineering from the NUST, Pakistan, in 1999, the M.Sc. degree in Telecomm Engineering (Optical Communication) from D.T.U. Denmark in 2004, and the Ph.D. degree in Mobile Communication from the University of Manchester, U.K., in 2011. He is currently the Chief Instructor at Engineering Wing, MCS, NUST, Pakistan. His research interests are in mobile and wireless communication, MIMO systems, compressed sensing for MIMO OFDM systems, massive MIMO systems, M2M for mobile systems, cognitive radio networks and cyber security. Abdul GHAFOOR obtained his Ph.D. in Control Systems in 2008 from University of Western Australia. Currently, he is Head of Information Security department at National University of Sciences and Technology, Pakistan. His research interests include model and controller reduction, image processing (enhancement, fusion, segmentation and watermarking), cognitive radios and ground penetration radar. Adil Masood SIDDIQUI received his bachelor degree in Telecommunications Engineering from Military College of Signals, Rawalpindi Pakistan in 1994, masters degree in Electronics and Telecommunication and Ph.D. in Electrical from University of Engineering and Technology, Lahore Pakistan, in 2005 and 2009 respectively. He is on the faculty of Military College of Signals, NUST Since 2009. His research interest includes image registration, de-noising, image enhancement and defogging. He has number of research publication at his credit.