Matrix Completion in Colocated MIMO Radar: Recoverability, Bounds&Theoretical Guarantees

It was recently shown that low rank matrix completion theory can be employed for designing new sampling schemes in the context of MIMO radars, which can lead to the reduction of the high volume of data typically required for accurate target detection and estimation. Employing random samplers at each reception antenna, a partially observed version of the received data matrix is formulated at the fusion center, which, under certain conditions, can be recovered using convex optimization. This paper presents the theoretical analysis regarding the performance of matrix completion in colocated MIMO radar systems, exploiting the particular structure of the data matrix. Both Uniform Linear Arrays (ULAs) and arbitrary 2-dimensional arrays are considered for transmission and reception. Especially for the ULA case, under some mild assumptions on the directions of arrival of the targets, it is explicitly shown that the coherence of the data matrix is both asymptotically and approximately optimal with respect to the number of antennas of the arrays involved and further, the data matrix is recoverable using a subset of its entries with minimal cardinality. Sufficient conditions guaranteeing low matrix coherence and consequently satisfactory matrix completion performance are also presented, including the arbitrary 2-dimensional array case.


4)
We then generalize our coherence results for the more general case of arbitrary 2-dimensional transmission and reception arrays, showing that the coherence of the corresponding data can be easily and tightly bounded by simply looking at the values of the squared magnitude of a 2-dimensional complex function over a properly chosen subset of the x/y plane, directly related to the target angles. Essentially, by choosing a candidate pair of transmission/reception array topologies, this general result produces coherence bounds in a straightforward way, also holding true almost surely. An important implication of the results presented in this paper is that the performance of matrix completion in colocated MIMO radar systems is completely independent of any other system design specification or target characteristic, except for the transmission/reception array topology, the target angles and possibly the wavelength of the carrier. That is, as far as matrix completion is concerned, the values of various important quantities, such as target reflection coefficients, Doppler shifts, pulse repetition intervals and the choice of the waveform dictionary are completely unconstrained. This fact makes matrix completion very appealing for reducing the number of samples needed for accurate detection and estimation in real world colocated MIMO radar systems. Also, compared to Compressive Sensing (CS) based MIMO radar, matrix completion has at least the same advantage in terms of sample reduction, justified by the strong theoretical guarantees presented here, while at the same time it avoids the angle discretization and basis mismatch issues inherent in CS-based approaches [12], [13], [14].
The paper is organized as follows. In Section II, we briefly introduce the required background in both noiseless and noisy matrix completion. We also restate the problem formulation for the MIMO radar case in a slightly more general form compared to [10]. In Section III, we present our coherence and recoverability results for ULA transmitter/receiver pairs, complete with detailed proofs and explanations. In Section IV, we present the generalization to the aforementioned coherence results for arbitrary 2-dimensional transmission/reception arrays, along with an instructive example. In Section IV, we state and prove a result for some special cases of spatial target configurations, completing our theoretical analysis. Finally, in Section V, we discuss further implications of our previously stated results and we present some simulations, validating their correctness.

A. Noiseless Matrix Completion: Problem Statement and Recoverability Conditions
Consider a generic complex matrix M ∈ C N 1 ×N 2 of rank r, whose compact Singular Value Decomposition (SVD) is given by M = UΣV H ≡ i∈N + r σ i (M) u i v H i and with column and row subspaces denoted as U and V respectively, spanned by the sets u i ∈ C N 1 ×1 i∈N + r and v i ∈ C N 2 ×1 i∈N + r , respectively.
Let P (M) ∈ C N 1 ×N 2 denote an entrywise sampling of M. In all the analysis that follows, we will adopt the theoretical frameworks presented in [4] and [5], according to which one hopes to reconstruct M from P (M) by solving the convex program minimize X * subject to X (i, j) = M (i, j) , ∀ (i, j) ∈ Ω , where the set Ω contains all matrix coordinates corresponding to the observed entries of M (contained in P (M)) and where X * represents the nuclear norm of X. In the following, we will refer to (1) as the Matrix Completion (MC) problem. Also in [4], the authors introduce the notion of subspace coherence, in order to derive specific conditions under which the solution of (1) coincides with M. The formal definition of subspace coherence follows, in a slightly more expanded form compared to the original definition stated in [4].

Definition 1. (Subspace Coherence [4])
Let U ≡ C r ⊆ C N be a subspace spanned by the set of orthonormal vectors . Also, define the matrix U [u 1 u 2 . . . u r ] ∈ C N ×r and let P U UU H ∈ R N ×N be the orthogonal projection onto U . Then, the coherence of U with respect to the standard basis As explained in [4], an intuitive motivation for defining subspace coherence stems from the fact that, in some sense, the singular vectors of the matrix under consideration need to be "sufficiently spread", or more precisely, need to be uncorrelated to the standard basis, in order for the matrix to be fully recoverable using only a small number of its entries.
The following assumptions regarding the subspaces U and V are of particular importance [4].
Indeed, if the constants µ 0 and µ 1 associated with the singular vectors of a matrix M are known, the following theorem holds.

Theorem 1. (Exact MC [4])
Let M ∈ C N 1 ×N 2 be a matrix of rank r obeying A0 and A1 and set N max {N 1 , N 2 }. Suppose we observe m entries of M with locations sampled uniformly at random. Then there exist constants C, c such that if for some β > 2, the minimizer to the program (1) is unique and equal to M with probability at least with the same probability of success.
If a matrix M obeys the assumptions A0 and A1 with parameters µ 0 and µ 1 , we will say that it obeys the incoherence property or, equivalently, that it is incoherent with parameters µ 0 and µ 1 .
In [5], the respective authors introduce a stricter assumption on the singular vectors of a generic matrix M, as a replacement for A0, enabling them to prove tighter -in fact, almost optimal-bounds on the number of observations required in order to achieve exact reconstruction of M by solving (1). Implicitly, they replace subspace coherence with a closely related quantity, which we will refer to as strong subspace coherence, whose definition is presented below.

Definition 2. (Strong Subspace Coherence)
Consider the hypotheses of Definition 1. Then, the strong coherence of U with respect to the standard basis Using the definition stated above, the authors in [5] essentially replace A0 by the following assumption, concerning the singular vectors of M.
If M obeys the assumptions A1 and A2 with a parameter µ ≥ max {µ s 0 , µ 1 }, we will say that it obeys the strong incoherence property or, equivalently, that it is strongly incoherent with parameter µ.
In addition, the following 2-in-1 theorem holds.

Theorem 2. (Exact MC I & II [5])
Let M ∈ C N 1 ×N 2 be a matrix of rank r obeying the strong incoherence property with parameter µ and set N max {N 1 , N 2 }. Suppose we observe m entries of M with locations sampled uniformly at random. Then, there exist positive numerical constants C 1 and C 2 such that if the minimizer to the program (1) is unique and equal to M with probability at least 1 − N −3 .
Further, it is easy to show that, in fact, incoherence implies strong incoherence (stated relatively informaly in [5]), as the following lemma asserts. Lemma 1. If a matrix M ∈ C N 1 ×N 2 of rank r is incoherent with parameters µ 0 and µ 1 , it is also strongly incoherent with parameter µ ≤ µ 0 √ r.
Proof of Lemma 1: See Appendix A.

B. Noisy Matrix Completion: Stability
In the previous subsection, we have focused on cases in which the matrix observations are perfectly noiseless. Of course, in any realistic setting, these observations will be corrupted by noise, yielding the observation model (for the same generic matrix M) where Z ∈ C N 1 ×N 2 constitutes a noise matrix with P (Z) F ≤ δ for some known constant δ > 0. If Z is random, then δ is such that P (Z) F ≤ δ with high probability. Then, instead of (1), the authors in [15] propose solving the program Indeed, under the same hypotheses of Theorem 2, it can be shown that the error norm M − M F is bounded from above as [15] with very high probability, where M denotes the solution to (9). In a nutshell, as the authors in [15] aptly explain, "when perfect noiseless recovery occurs, then matrix completion is stable vis a vis perturbations". Consequently, if M exhibits favorable coherence properties, both noiseless and noisy matrix completion will be more realistic. Therefore, in order to guarantee satisfactory performance for matrix completion, it suffices to study the conditions under which the coherence of M will be as low as possible.

C. Matrix Completion in Colocated MIMO Radar
We consider the respective problem formulation proposed in [10] (see Subsection A of Section II in [10]). Extending the problem to the case of arbitrary 2-dimensional arrays in an obvious way [16], the matrix to be completed at the fusion center of the receiver, P (Y), obeys the special observation model where M r and M t denote the numbers of reception and transmission antennas, respectively, Z is an interference/observation noise matrix as defined above and where X r ∈ C M r ×K (respectively for X t ∈ C M t ×K ) constitutes an alternant matrix defined as with the sets [x r l y r l ] T l∈N M r −1 and {θ k } k∈N K−1 containing the 2-dimensional antenna coordinates of the reception array and the target angles, respectively and λ denoting the carrier wavelength utilized for the communication, and where D ∈ C K×K constitutes a non -zero -diagonal matrix defined as where the sets {ζ k } k∈N K−1 and {ϑ k } k∈N K−1 contain the target reflection coefficients and target speeds, respectively and q and T P R denote the pulse index and the pulse repetition interval, respectively. For the simplest ULA case (as treated in [10]), where d r(t) denotes the respective array antenna spacing, and X r and X t degenerate to Vandermonde matrices.
In the next sections, we focus almost exclusively on bounding the coherence of ∆, first for the ULA case and then for the more general arbitrary 2-dimensional array case. Also, when possible, we derive sufficient conditions under which the coherence the aforementioned matrix is small.

III. COHERENCE AND RECOVERABILITY OF ∆ FOR ULA TRANSMITTER -RECEIVER PAIRS
In this section, we present our coherence and recoverability results for the case in which ULAs are utilized for transmission and reception. In short, we prove: • Asymptotic and approximate optimality of the coherence of ∆ with respect to the number of transmission/reception antennas and • Near optimal recoverability of ∆ via matrix completion.
A. Coherence of ∆ Theorem 3. (Coherence for ULAs) Consider a Uniform Linear Array (ULA) transmitter -receiver pair and assume that the set of target angles {θ k } k∈N K−1 consists of almost surely distinct members. Then, for any fixed M t and M r , as long as the associated matrix ∆ obeys the assumptions A0 and A1 with with probability 1. In the above, for k ∈ {t, r} and (25) Further, if ξ min {ξ r , ξ t } = 0, then, for any fixed K, as long as min i∈{t,r} where (21) and (22) hold replacing both β ξ t (M t ) and β ξ r (M r ) by the constant β ξ (that is, independent of both M t and M r ). Additionally, in the limit we respect to M t and M r , we have that is, the coherence of ∆ is asymptotically optimal. Finally, if ξ is safely bounded away from zero, then, for sufficiently large M t and M r , it is true that that is, the smallest possible coherence for ∆ can be approximately attained even for finite values of M t and M r .
Before we proceed with the proof of the theorem, let us state the following standard result, which will help us develop our arguments easily and concretely.
Then, it is true that Further, equality holds on the left (right) of (31) if and only if equality holds on the left (right) of (32) if and only if the N − 1 largest (smallest) eigenvalues are equal.
Proof of Theorem 3: In order to make it more tractable, we divide the proof into the following two subsections. In the first subsection, we present a suitable characterization of the SVD of ∆ which will come in handy in identifying the essential actions needed to be taken in order to bound its coherence. However, the methodology presented is very general and can be applied to any given rank-L matrix M, as long as it can be explicitly written as the product M = M 1 DM 2 ∈ C M 1 ×M 2 , with D ∈ C L×L being an arbitrary full rank matrix. In the second subsection, we use the results from the first, as well as the special structure of ∆ in order to derive quantitatively useful results regarding its coherence.

1) Characterization of the SVD of ∆:
We would like to study the coherence of the almost surely rank-K matrix where the Vandermonde matrix X r ∈ C M r ×K (respectively for X t ∈ C M t ×K ) is defined by the generating vector with and D ∈ C K×K is an arbitrary non -zero -diagonal matrix. Since ∆ is assumed to be of rank-K almost surely, we implicitly consider the case where the set of angles {θ k } k∈N K−1 consists of almost surely distinct members. In general, the compact SVD of ∆ can be expressed as where U ∈ C M r ×K , V ∈ C M t ×K such that U H U = I K , V H V = I K and Σ ∈ R K×K constitutes a diagonal matrix containing the (non zero) singular values of ∆.
Respectively for X t , consider the thin QR decomposition of X r given by respectively for Q r ) and Λ ∈ R K×K is non -zero -diagonal, containing the singular values of A r DA T t . Thus, we arrive at the expression consequently, by the uniqueness of the singular values of a matrix, Λ ≡ Σ. Therefore, we can set or, equivalently, where (39) stems from the fact that the columns of X r are linearly independent almost surely and, as a result, A r is almost surely invertible. Likewise, regarding the coherence of the row space of ∆, we get 2) Effective Bounding of λ min X H t(r) X t(r) : In the following, we will mainly focus on the matrix X H t X t , since the respective analysis for X H r X r is identical. Due to (41), we need a strictly positive lower bound for λ min X H t X t , with where Let us now apply Theorem 4 to the almost surely positive definite matrix M X H We also need the trace of M 2 . Since M is a Hermitian matrix, it is true that At this point, it is instructive to at least qualitatively study the behavior of the square of φ M (x) (for a general parameter M ∈ N + ) defined above 1 . Fig. 1 shows the square of the function for three different values of M . We can directly identify the following useful fact: then the entire sequence of local maxima of φ 2 M (x) is strictly decreasing. Next, define the function g : and let ξ t min The motivation for defining ξ t stems from the fact that the function φ 2 M (x) is both periodic with unitary period and symmetric and thus it suffices to study its behavior only for x ∈ 0, 1 2 . Then, due to Fact 1, we can upper bound (46) as Consequently, by Theorem 4, and consequently we can bound λ min (M) ≡ λ min X H t X t from below as Respectively, we get Therefore, for fixed M t and M r , as long as and (56) both hold true with probability 1. Consequently, Now, assume that ξ min {ξ r , ξ t } = 0. Then, we can write Since ξ = 0 by assumption and due to Fact 2, the supremum appearing in (59) will be always finite and, consequently the respective bound will be non trivial. Therefore, in this case, for fixed K, (55) becomes min i∈{t,r} Passing to the limit with respect to M t (respectively M r ), we get lim sup and since µ (U ) ≥ 1 by definition [4], it must be true that, in the limit, µ (U ) ≡ 1. Likewise, it will also be true that, in the limit, µ (V ) ≡ 1.
If additionally ξ is safely bounded away from zero, then β ξ will be small (due to Fact 1) and thus for sufficiently large but finite M t and M r , An experimental calculation of the square root of the supremum β ξ for ξ ∈ 10 −3 , 0.5 shown in Fig. 3 (in logarithmic scale) can validate and possibly strengthen our theoretical arguments presented above. We observe that β ξ over ξ constitutes a hyperbolic function, converging rapidly to 1 (linear scale), which corresponds to its minimum value. Finally, regarding the Assumption A1, by a simple argument involving the Cauchy -Schwarz inequality, it can be shown that [4], in the general case, one can choose holding true also with probability 1. The results presented in the statement of Theorem 3 readily follow.
In colocated MIMO Radar systems, due to the need for unambiguous angle estimation (target detection), it is very common to assume that θ i ∈ [−π/2, π/2] , ∀ i ∈ N K−1 . Also, especially for the case where ULAs are employed for transmission and reception, another common assumption is to choose d r ≡ d t = λ/2. Under this setting, the following lemma provides a simple sufficient condition, which guarantees that the asymptotics of Theorem 3 hold true and, as a result, that for a sufficiently large number of transmission/reception antennas, the coherence of ∆ will be small.

Lemma 2. (ULA Pairs Coherence Control) Consider the hypotheses and definitions of Theorem 3. Set d r ≡ d t = λ/2. If additionally
∀ (i, j) ∈ N K−1 × N K−1 with i = j and for some apriori chosen η ∈ 0, π 2 , then and the asymptotics of Theorem 3 always hold true. In particular, the higher the value of η, the higher the value of ξ and the lower the coherence of ∆.
Proof of Lemma 2: See Appendix B.

B. Near Optimal Recoverability of ∆
Using Lemma 1, we can now directly combine Theorem 2 with the coherence results presented in the previous subsection, producing (asymptotic) bounds regarding the number of observations required for the exact reconstruction of the matrix ∆ by solving the convex program (1). Specifically for ULA transmitter/receiver pairs, we present the following interesting result. Since the proof is straightforward, it is omitted.

Theorem 5. (Near Optimal Recoverability for ULA Pairs) Consider the hypotheses of Theorem 3 and assume that
for a fixed number of targets K, ∆ is strongly incoherent with parameter and there exist positive numerical constants C 1 and C 2 such that if the minimizer to the program (1) is unique and equal to ∆ with probability at least 1 − M −3 .
Roughly speaking, Theorem 5 implies that as long as ULAs are concerned, for a sufficiently large number of transmission and reception antennas and for a fixed and relatively small number of targets, matrix completion is exact if the number of observations is at least of an order of M polylog (M ), that is, matrix completion is exact for a slightly larger number of observations than the information theoretic limit (see [5] for details).

IV. COHERENCE OF ∆ FOR ARBITRARY 2D ARRAYS
It is possible to generalize Theorem 3 for a far more general case, that is, when the transmitter and the receiver employ arbitrary 2-dimensional arrays. However, in this case, since our knowledge about the specific characteristics of the topologies of the arrays involved is very restricted, our bounds, although tight, are not expected to be as easily handleable as in the ULA case (see Theorem 3 and Lemma 2). Next, we state and prove the following theorem in this respect.

Theorem 6. (Coherence for Arbitrary 2D Arrays)
Consider an arbitrary array transmitter -receiver pair equipped with M t and M r antennas, respectively. Assume that the set of target angles {θ k } k∈N K−1 consists of almost surely distinct members and that where A constitutes a nominal point set for all admissible angle pair combinations. Also, let the abstract sets T and R contain all the essential information regarding the transmitter and receiver topologies, also assumed fixed and known apriori. Then, for any M t and M r , as long as the associated matrix ∆ obeys the assumptions A0 and A1 with with probability 1 and where with ϕ t(r) : A → C given by where Proof of Theorem 6: Again, we divide the proof into the following subsections, in similar fashion as in the proof of Theorem 3.
1) Characterization of the SVD of ∆: We now consider the almost surely rank-K matrix exactly as defined in Subsection C of Section II. Of course, since ∆ is assumed to be of rank-K almost surely, the members of the set of angles {θ k } k∈N K−1 are implicitly assumed to be almost surely distinct. By almost identical reasoning as in the proof of Theorem 3, the coherences of the column and row spaces of ∆, U and V , can be upper bounded using (41) and (42), respectively.
2) Bounding λ min X H t(r) X t(r) : We directly focus on the matrix X H t X t ∈ C K×K defined as in (43), where this time, Applying Theorem 3 to M X H t X t ∈ C K×K , we get τ ≡ M t and, concerning the trace of M 2 , it is true that Let all the assumptions of the statement of Theorem 6 hold true. Then, we can define a bivariate function ϕ t : A → C given by 2 whose norm can be bounded as Observe that in the expressions above, the supremum is taken conditional on the set T and, as a result, it is highly dependent on the array topology of the transmitter and therefore also on M t , but of course independent of any combination of the angles. Then, we can bound tr M 2 as and the results follow using similar procedure to the respective part of the proof of Theorem 3. Remark 1. Indeed, one may claim that Theorem 6 is mostly of theoretical value and that its practical applicability is limited. On the one hand, this is true, since, except for the ULA case, for which explicit results are available (see Theorem 3  bounding norms of sums of complex exponentials, whose exponents are arbitrary real variable functions constitutes a difficult mathematical problem. However, from an engineering point of view, for a given pair of transmitter -receiver topologies, we can always compute the aforementioned supremum empirically, as it becomes clear by the following example. suggests that in order to bound the coherence of the respective matrix ∆, a uniformly sampled version of which is available at the receiver's fusion center, we have to specify the supremum given by (75), which, of course, cannot be computed analytically. Fig. 4(a) shows the function ϕ t(r) (x, y |T (R) ) 2 with respect to (x, y) ∈ [−π, π] 2 . We observe that this function is periodic in the 2-dimensional plane, with period equal to 2π in each dimension.
Let us now assume that for some η ∈ (0, π), that is, every pair of distinct angles θ i and θ j are such that the magnitudes of their differences are lying in two non intersecting halfplanes, one above and one below the hyperplane y = x, within a margin of η. Empirically, using the graph of ϕ t(r) (x, y |T (R) ) 2 , we can easily specify its supremum over the set A, which is required in order to bound the coherence of ∆. Additionally, it is obvious that if η is sufficiently large, the coherence of ∆ will be essentially relatively small. Interestingly, this fact draws immediate connections regarding the coherence between the UCA and the ULA case (see Theorem 3 and Lemma 2). The function ϕ t(r) (x, y |T (R) ) 2 resulting from the application of Theorem 6 for the ULA case is shown in Fig. 4(b). We observe that the sufficient condition for low coherence of ∆ presented in Lemma 2 can be immediately validated.
Comparing the two graphs shown in Fig. 4, we can infer that in the UCA case the allowable region for the magnitudes of the differences of the angle pairs, given by the set A, is larger than the respective region for the ULA case (Lemma 2). On the other hand, the values of ϕ t(r) (x, y |T (R) ) 2 for the ULA case in the interior of the allowable region are considerably smaller than the values of the respective function in the interior of the respective set for the UCA case. Consequently, regarding our choice of transmission/reception arrays, there is an obvious trade -off between "resolution" and coherence.
Remark 2. There are other fancier types of 2-dimensional arrays that can achieve a much better "resolution/coherence ratio". For instance, we have found experimentally that carefully designed spiral arrays, whose antenna positions constitute a sampling of the usual Archimedean Spiral, possess the advantages of both the aforementioned cases and, additionally, they exhibit very good asymptotic properties, guaranteeing low coherence for a sufficiently large number of antennas.
Until now, in all the results we have presented, we have assumed that the target angles θ k , k ∈ N K−1 are almost surely distinct. Apparently, this required property of distinctness is far weaker than (statistical) independence. In fact, our results presented in detail in the previous sections continue to hold without any modification for any set of dependent target angles, as long as they are all different from each other with probability 1 (recall the Vandermonde/alternant structure of the matrices X r and X t in the proofs of Theorems 3 and 6). Therefore, regarding the coherence of ∆ for arbitrary 2-dimensional arrays (and thus also for ULAs), the only case that needs special treatment is when θ i ≡ θ j for some (i, j) ∈ N K−1 × N K−1 with i = j, for which we present and prove the following result.

Theorem 7. (Coherence for Non -Distinct Angles)
Consider an arbitrary 2-dimensional array transmitter -receiver pair equipped with M t and M r antennas, respectively. Assume that the set of angles Θ {θ k } k∈N K−1 is such that it can be partitioned as where D ⊆ Θ contains almost surely distinct members and Let ∆ and ∆ D be the matrices associated with the angle sets Θ and D, respectively. Then, it is true that Proof of Theorem 7: Consider the matrix where X r ∈ C M r ×K , X t ∈ C M t ×K and D ∈ C K×K are defined as in the proof of either Theorem 3 or Theorem 6. Let the assumptions of the statement of Theorem 7 hold true. Then, only |D| L columns of both X r and X t will be almost surely linearly independent, whereas the rest |R| ≡ K − L columns of both matrices constitute repetitions of the aforementioned L ones. As a result, ∆ will be almost surely of rank L.
Let us re-express ∆ as where P ∈ R K×K constitutes an appropriately chosen permutation matrix such that where X D r ∈ C M r ×L (respectively for X D t ∈ C M t ×L ) contains the columns of X r associated with the almost surely distinct angles in D and X R r ∈ C M r ×K−L (respectively for X R t ∈ C M t ×K−L ) contains the rest of columns of X r , associated with the rest of the angles in R. Of course, D ∈ C K×K constitutes a non -zero -diagonal matrix.
Respectively for X t , the thin QR decomposition of X r can be expressed as A r ∈ C K×K is a specially structured singular upper triangular matrix (see expressions above) of rank L and A D r ∈ C L×K constitutes a rectangular matrix also of rank L.
Let V D Then, based on (93) and using an almost identical procedure as in the first part of the proof of Theorem 3, we can directly show that the coherence of the column space of ∆, U , is given by Respectively, the coherence of the row space of of ∆, V , is given by Now, consider the almost surely rank-L matrix where the diagonal matrix D D ∈ C L×L is defined in an obvious way (see (90) -(92)). Then, by construction of the QR decomposition, it must be true that where, A D t ∈ C L×L and A D r ∈ C L×L constitute almost surely full rank matrices. Recall (38) and adapt it appropriately for expressing the coherences of the column and row spaces of ∆ D , U D and V D , respectively. Our claims follow. Remark 3. Indeed, in many applications (Radar and non -Radar), it is very likely that the situations Theorem 7 is dealing with may correspond to events of zero measure. However, we feel that stating this result is important, in order for the coherence analysis we presented in the previous chapters to be entirely complete. Also, interestingly, the simple implication of Theorem 7 is somewhat not intuitive: As the difference between two angles is decreasing, the coherence of ∆ becomes worse (that is, increases), but if the difference is exactly zero, then the coherence of ∆ is identical to the coherence of the variation of ∆ resulting from simply removing the information corresponding to any of the two identical angles. Clearly, this result does not in any way contradict the ones presented in the previous sections.

VI. DISCUSSION AND SOME SIMULATIONS
In this section, we present some simulations, validating our main results presented above and discuss some further implications of our respective theoretical analysis.
For simplicity, we consider a MIMO radar system equipped with identical ULAs for transmission and reception, with d r ≡ d t = λ/2 and M r ≡ M t M . We also consider K = 4 targets in the far field, with angles independently distributed in − π 2 , π 2 . In this synthetic example, in order to demonstrate the validity of Theorem 3, we assume that the target angles are known apriori. By Lemma 2, we know that the condition ξ = 0 will always hold and consequently the asymptotics of Theorem 3 must also hold true. Of course, ξ can be computed either using (24) or (66) (for some sufficiently chosen value of η), with the latter producing a worst -case bound regarding the coherence of the associated matrix ∆. Also, in this example, we obviously have µ (U ) ≡ µ (V ).
Using (24) for the computation of ξ, Fig. 5 shows the behavior of both the coherence of ∆ and its bound µ 0 , which results by directly applying Theorem 3, as a function of the number of transmission/reception antennas M . We observe that, clearly, the proposed bound is tight and it tracks the convergence of the coherence of ∆ to unity very accurately. We should mention here that for very small angle differences, the bound becomes somewhat looser. However, our numerical simulations have shown that our bound constitutes a very reasonable coherence estimate in all cases.  Apparently, in any realistic situation, the actual values of the target angles are unknown. Assuming generically that each of the angle differences belongs to a set given by (65) for some η ∈ 0, π 2 -η depends on the specific radar application-, we can invoke Lemma 2 in order to bound the coherence of ∆ in this more general case. Fig. 6 depicts a number of bounds produced by Lemma 2 for various values of η, as functions of the number of antennas M . One can observe that, as the value of η increases, the respective coherence bound converges much faster to unity, therefore increasing our confidence that the performance of matrix completion will be satisfactory for a relatively smaller number of transmission/reception antennas.
However, we should stress that Lemma 2 essentially produces worst case bounds, which might be too pessimistic for specific applications. If this is the case, one could use Theorem 6, which provides greater versatility for deriving more accurate bounds for more specific target configurations and for given number of antennas or, alternatively, one could derive variants of Lemma 2 for special target configurations.
Another important ULA configuration in MIMO radar systems results by choosing d t = M r λ/2 and d r = λ/2. It is well known that this particular choice for the transmitter antenna spacing increases the degrees of freedom of the system to M t M r using only M t + M r physical antenna elements and consequently, higher spatial resolution can be obtained (see, for instance, [18]). If we are interested in the performance of matrix completion, as far as µ (V ) is concerned, associated solely with the reception array, we can directly use Theorem 3 in conjunction with Lemma 2 as explained above in order to derive the respective coherence bound. However, the behavior of µ (U ) is much more complicated and the application of Theorem 3 leads to an unreasonably involved analysis. But one could invoke Theorem 6 in this case. Fig. 7(a) shows the function |ϕ t (x, y |T )| with respect to (x, y) ∈ [−π, π] 2 . Assuming that the angles are independently and uniformly distributed in − π 2 , π 2 and that the contours of |ϕ t (x, y |T )| 2 are sufficiently dense (for M r properly chosen), then the respective values of the aforementioned function will be essentially small, since, technically speaking, the probability of any θ i , θ j belonging to the union of the strict subsets of − π 2 , π 2 2 corresponding to the contours of |ϕ t (x, y |T )| 2 shown in Fig. 7(a) will be essentially zero. Therefore, a low value for µ (U ) is guaranteed with very high probability.

VII. CONCLUSION
In this paper, we have presented a detailed analysis regarding the recoverability of the data matrix in colocated MIMO radar systems via convex optimization (matrix completion), for a number of commonly used array configurations. We showed that, in most cases, the data matrix is indeed recoverable from a minimal number of observations, as long as the number of transmission and reception antennas is sufficiently large and under common assumptions on the DOAs of the targets. Consequently, the matrix completion approach for reducing the sampling requirements in colocated MIMO radar is indeed theoretically robust and also appealing for practical consideration in real world applications. However, although we have explicitly shown that the choice of ULAs for transmission and reception leads to asymptotically and approximately optimal coherence of the data matrix, the important and more general problem of optimally choosing the array topologies for minimizing matrix coherence still remains open, clearly suggesting new directions for further research.

APPENDIX A PROOF OF LEMMA 1
Let the hypothesis of the statement of Lemma 1 hold true. In the following, we consider only the column space of M, U , since, for V the procedure is identical. First, consider the set G (i, j) ∈ N + N × N + N |i ≡ j . Then, In all cases, it is true that µ s (U ) ≤ µ 0 and µ s (V ) ≤ µ 0 .
In the following, our goal will be to explicitly specify the infimum and the supremum appearing in (103), or equivalently the set F .