Supplementary Material for "Multi-User MIMO-OFDM ISAC for Low-Altitude UAV with Zero Sensing Resource Allocation"

1 Supplementary Material for “Multi-User MIMO-OFDM ISAC for Low-Altitude UAV with Zero Sensing Resource Allocation” Zhiwen Zhou, Yong Zeng, Fellow, IEEE, Chunguo Li, Senior Member, IEEE, Fei Yang, Yan Chen, Senior Member, IEEE, and Jingon Joung, Senior Member, IEEE I. CLOSED-FORM OPTIMAL BEAMFORMING FOR THE SEARCHING STAGE In this section, we provide a closed-form solution to the following problem, min fu,q ∥fu,q∥2 s.t.gH 1fu,q≥r1, gH 2fu,q≥r2. (1) Theorem 1: The optimal solution to problem (1) is f⋆ u,q =         r1 ∥g1∥2ejϕ1g1,if r2≤r1 ∥g1∥2gH 2g1, r2 ∥g2∥2ejϕ2g2,if r2≥r1 gH 1g2 ∥g2∥2, GSr⋆,otherwise, (2) where the phases ϕ1, ϕ2can be chosen arbitrarily, G≜ [g1g2],K≜GHG=∥g1∥2gH 1g2 gH 2g1∥g2∥2,S≜K−1= S11 S12 S∗ 12 S22,φ⋆ 2=π−∠S12, and r⋆≜r1 r2ejφ⋆ 2. Proof: We first consider the case when g1,g2are linearly dependent. Assume g2=αg1with α∈Cand g1=0. Then the two constraints in (1) act along the same direction and reduce to gH 1fu,q≥r1and |α|gH 1fu,q≥r2, i.e., gH 1fu,q≥Rwith R≜maxr1,r2 |α|.(3) By the Cauchy–Schwarz inequality, gH 1fu,q≤ ∥g1∥∥fu,q∥, hence every feasible point obeys ∥fu,q∥ ≥ R/∥g1∥and therefore ∥fu,q∥2≥R2/∥g1∥2. This lower bound is attainable by f⋆ u,q =R ∥g1∥2ejϕg1, ϕ ∈R.(4) Next, we consider the case where one of the constraints is redundant. Assume g1,g2are linearly independent. If r2≤r1 ∥g1∥2gH 2g1,(5) then the second constraint is implied by the first one. Taking f⋆ u,q =αg1,with |α|=r1 ∥g1∥2,(6) we have |gH 1f⋆ u,q|=r1and |gH 2f⋆ u,q|=|α||gH 2g1|=r1 ∥g1∥2|gH 2g1| ≥ r2.(7) By the Cauchy–Schwarz inequality, (6) also attains the minimum norm permitted by the first constraint, hence it solves (1). The optimal value is  f⋆ u,q  2=r2 1 ∥g1∥2.(8) Symmetrically, if r1≤r2 ∥g2∥2gH 1g2,(9) then the first constraint is implied by the second one, and the minimum-norm feasible point is f⋆ u,q =βg2,|β|=r2 ∥g2∥2, f⋆ u,q  2=r2 2 ∥g2∥2.(10) In either redundant case, the phase of αor βcan be chosen arbitrarily. Next, we consider the general case where g1,g2are linearly independent and the two constraints are non-redundant. We first propose the following lemma. Lemma 1: When g1,g2are linearly independent, r1gH 2g1< r2∥g1∥2and r2gH 1g2< r1∥g2∥2, for the optimal solution f⋆ u,q of problem (1), the constraints are tight, i.e., gH 1f⋆ u,q=r1and gH 2f⋆ u,q=r2. Proof: Please refer to Section II. By Lemma 1, we enforce GHfu,q =r(φ1, φ2)≜r1ejφ1 r2ejφ2.(11) For fixed phases, the minimum-norm feasible vector is the orthogonal projection fu,q(φ1, φ2)=G(GHG)−1r(φ1, φ2) = GSr(φ1, φ2), (12) with squared norm ∥fu,q(φ1, φ2)∥2=r(φ1, φ2)HSr(φ1, φ2).(13) Writing S=S11 S12 S∗ 12 S22, setting φ1= 0, we obtain ∥fu,q(0, φ2)∥2=r2 1S11 +r2 2S22 + 2r1r2ReS12ejφ2. (14) Choosing φ⋆ 2=π−∠S12 minimizes the real part and yields Re S12ejφ⋆ 2=− |S12|. Thus, the optimal solution to problem (1) can be obtained as f⋆ u,q =GSr⋆=GGHG−1r⋆,  f⋆ u,q  2=r2 1S11 +r2 2S22 −2r1r2|S12|. (15) 2 II. PROOF OF LEMMA 1 First, we prove that at least one constraint is tight. For any feasible fu,q, let c1≜|gH 1fu,q|,c2≜|gH 2fu,q|, and r≜max{r1/c1, r2/c2}∈(0,1]. Then ˜ fu,q ≜rfu,q is feasible with ∥˜ fu,q∥2=r2∥fu,q∥2≤ ∥fu,q∥2, and at least one constraint is tight at ˜ fu,q. We next prove that for the optimal solution f⋆ u,q, both constraints are tight, i.e., the case with only one constraint being active is impossible. By symmetry, assume a minimizer fu,q obeys |gH 1fu,q|=r1and |gH 2fu,q|> r2. Let P1≜ g1gH 1/∥g1∥2and decompose fu,q =αg1+z,z≜(I−P1)fu,q ⊥g1.(16) Then |α|∥g1∥2=gH 1fu,q=r1and ∥fu,q∥2=r2 1 ∥g1∥2+∥z∥2.(17) Define p≜(I−P1)g2=0(by linear independence) and let s≜αgH 2g1,c≜gH 2z=pHz,y2≜s+c=gH 2fu,q. Thus |y2|> r2. By Cauchy–Schwarz inequality, |c|=|pHz| ≤ ∥p∥∥z∥, and for any prescribed c, min z⊥g1,pHz=c∥z∥=|c| ∥p∥,attained at z=c ∥p∥2p.(18) Note that under the non-redundancy assumptions r1gH 2g1< r2∥g1∥2and r2gH 1g2< r1∥g2∥2, we have for any feasible point with |gH 1fu,q|=r1that |s|=|α|gH 2g1=r1 ∥g1∥2gH 2g1< r2.(19) Next we find a smaller |c|that keeps feasibility. Among all ˜c∈Csatisfying |s+ ˜c|=r2, the choice colinear with s minimizes |˜c|; in particular c⋆≜r2ej∠s−s, |c⋆|=r2− |s|.(20) Together with |y2|> r2, this implies, by the reverse triangle inequality, |c|=|y2−s|≥|y2|−|s|> r2− |s|=|c⋆|.(21) Define z⋆≜c⋆ ∥p∥2p,f⋆ u,q ≜αg1+z⋆.(22) Then z⋆⊥g1and pHz⋆=c⋆, so gH 1f⋆ u,q=r1,gH 2f⋆ u,q=|s+c⋆|=r2,(23) i.e., f⋆ u,q is feasible and both constraints are tight. Moreover, by (18) and |c⋆|<|c|, ∥f⋆ u,q∥2=r2 1 ∥g1∥2+|c⋆|2 ∥p∥2<r2 1 ∥g1∥2+|c|2 ∥p∥2≤ ∥fu,q∥2, (24) contradicting the minimality of fu,q. Hence the case with only one active constraint is impossible. By symmetry, when g1,g2are linearly independent, r1gH 2g1< r2∥g1∥2and r2gH 1g2< r1∥g2∥2, both constraints must be tight at any minimizer. III. COMPUTATIONAL COMPLEXITY ANALYSIS FOR THE SENSING ALGORITHM We summarize the per-stage and end-to-end sensing complexity as below. For the spatial-domain denoising step, element-wise division costs O(MNPQ). Forming the delay–Doppler tensor by 2D FFTs costs O(MNPQ log(P Qb)) for searching and O(MNPQ log(P Q)) for tracking, and thresholding adds O(MNPQ). For angle sensing with 2D spatial smoothing and MUSIC, building the subarray covariances over I×Jsubarrays of size Msub ×Nsub costs OIJPQ(MsubNsub)2, followed by an EVD of size MsubNsub, i.e., O(MsubNsub)3. Evaluating the MUSIC spectrum is quadratic in MsubNsub per tested angle pair, and therefore scales linearly with the number of angle grid points used in practice. For delay–Doppler sensing, the ZF receive beamforming is calculated for all KAangles with OMNK2 A+K3 A. Forming YkAcosts O(MNPQ)per angle. The periodogram (2D FFT) per angle costs O(PQblog(P Qb)) for searching and O(PQ log(P Q)) for tracking. The element-wise divisions and amplitude estimates are O(PQ)per angle and are dominated by the FFT part. Assuming KAis small, the dominant end-to-end sensing complexity for the searching stage is O(MNPQ log(P Qb))+OIJPQ(MsubNsub)2 +O(MsubNsub)3,(25) and for the tracking stage, O(MNPQ log(P Q))+OIJPQ(MsubNsub)2 +O(MsubNsub)3.(26) In typical settings, the dominant contributors are the covariance accumulation O(IJP Q(MsubNsub)2)and the EVD O((MsubNsub)3).