{'fraction_non_alphanumeric': 0.05036558012176294, 'fraction_numerical': 0.02586734248011885, 'mean_word_length': 3.9303461151802384, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Robustness of Two-Dimensional Line Spectral Estimation Against Spiky Noise

The aim of two-dimensional line spectral estimation is to super-resolve the spectral point sources of the signal from time samples. In many associated applications such as radar and sonar, due to cut-off and saturation regions in electronic devices, some of the numbers of samples are corrupted by spiky noise. To overcome this problem, we present a new convex program to simultaneously estimate spectral point sources and spiky noise in two dimensions. To prove uniqueness of the solution, it is sufficient to show that a dual certificate exists. Construction of the dual certificate imposes a mild condition on the separation of the spectral point sources. Also, the number of spikes and detectable sparse sources are shown to be a logarithmic function of the number of time samples. Simulation results confirm the conclusions of our general theory.


I. INTRODUCTION
Multiple-dimensional line spectral estimation (LSE) has received much attention in signal processing society in recent years. It is a fundamental concern of many applications such as Multiple-Input Multiple-Output (MIMO) radar [1], superresolution imaging [2] and channel estimation in wireless communications [3]. Specifically, in the MIMO radar, there exist multiple transmit antennas which emit probing signals to the target, a reflected version of these signals is then received by multiple receiver antennas. One can super-resolve the triples relative angle, Doppler shifts, and delay to estimate the location and velocities of the targets. In the LSE setting, a linear combination of r sinusoidal with arbitrary complex amplitude should be observed. In practice, a subset of the observations is corrupted by spiky noise due to cut-off and saturation in electronic devices. In this paper, we address the two-dimensional LSE problem in the presence of spiky noise.
Parametric approaches in the LSE problem are based on dividing the observation space into signal subspace and noise subspace by singular value decomposition [4], [5]. Although the computational complexity of these approaches is low, the sensitivity to additive perturbation is high. Also, they can not determine the location of spiky noise and require prior knowledge of number of spectral sources.
In another field of study, known as compressive sensing, an exact solution can be achieved in an underdetermined linear system by assuming that the signal of interest is sparse in a known discrete dictionary [6], [7], here the Fourier domain. Therefore, 1 minimization can be used to recover the support of the signal on DFT basis. However, in many practical applications such as radar and sonar, the spectral sources belong to a continuous dictionary. Thereby, mismatch between the actual sources and DFT basis is inevitable [8] [9].
In [10], it is shown that refining the grid exceedingly raises computational complexity. Further, 1 minimization dose not achieve an exact solution in the ultrahigh-dimensional setting.
In [11], Candes and Fernandez have proposed a nonparametric approach to super-resolve the inherent frequencies in (1) for one and two dimensional cases. Their approach is based on Total-Variation (TV) norm minimization which is used to promote the sparsity of a continuous function. It has been shown that a linear combination of the fourth power of Dirichlet kernel and its derivatives can be used to construct a valid certificate to this problem. This construction imposes a minimum separation 4/n and 4.76/n between the frequency sources in one and two dimensions, respectively. To achieve sharp bound on minimum separation in onedimensional case, [12] has constructed the dual certificate by three Dirichlet kernels with different cut-off frequencies. Also, [13] has extended this kernel to two-dimensional situation. The imposed minimum separations respectively are 2.52/n and 3.36/n. In [14], one-dimensional signal is observed in a random subset of time instances. Tang et.al. have proved that under a mild assumptions on the minimum separation and with O(r log r log n) partial time samples, one can always find the random trigonometric polynomial that estimates the point sources. Their approach has been extended to two-dimensional case in [15].
Additive noise is inevitable in most of the mentioned applications. Recently, a significant line of study is focused on support stability of TV norm minimization when the measurements are corrupted by additive perturbation [16]. Establishing a trade-off between noise power and TV norm, known as BLASSO, is a common way to deal with such a problem [17], [18]. [19] made a precise comparison between robustness of optimization based methods and conventional approaches dealing with additive noise. Due to sensor failure, another kind of corruption that may appear in the applications is spiky noise. Subspace decomposition approaches are not able to estimate the sources' frequencies when a subset of time samples is corrupted by spiky noise. Precisely, they are designed to overcome Gaussian-like noise and are relatively ill-positioned in front of spiky noise. [20] has suggested a convex optimization program that incorporates the sparsity feature of spiky noise in the cost function in order to simultaneous estimation of both spectral sources and spiky noise in a one-dimensional situation. Although many related works in the literature have revolved around one dimension, but many applications such as superresolution imaging and MIMO radar require multi-dimensional analysis.
In this paper, our main contribution is to construct a valid dual certificate for two-dimensional case. Our certificate is a two-dimensional trigonometric low-pass polynomial that interpolates any sign pattern of the signal. Further, its coefficients belong to relative interior of sub-differential of 1 norm. It is shown that if the number of the spectral sources and the spiky noise samples is restricted by a logarithmic function of the number of samples, our semidefint programing achieves an exact solution under mild condition on the separation between the spectral sources. [21] has proposed an innovative approach based on matrix completion that simultaneously super-resolves the spectral sources and detects spiky noise in two-dimensional case. It also proved that Enhanced Matrix Completion (EMaC) achieves an exact solution if the sample complexity exceeds O(r 2 log 3 n 2 ), under some incoherence conditions.
The inherent infinite dimension of the LSE problem is apparently an enormous challenge. One can approximate the problem on a fine grid [22] or solve the TV norm minimization directly by linear programing [23]. [11] has converted the dual of TV norm minimization to linear matrix inequality (LMI) using positive trigonometric polynomial (PTP) theory [24]. The magnitude of the trigonometric polynomial in each subband of its frequency domain is controllable by the coefficients that are obtained from PTP theory [25]- [27]. Finally, we present numerical simulations to justify our results.
The rest of the paper is organized as follows. The problem is formulated in Section II. Penalized TV norm minimization and our main theorem in two-dimensional case are presented in section III. Construction of dual certificate and implementation of the dual problem are given in Sections IV and V, respectively. Section VI is devoted to numerical experiments. Finally, conclusions are discussed in Section VII.
Notation. Throughout the paper, scalars are denoted by lowercase letters, vectors by lowercase boldface letters, and matrices by uppercase boldface letters. The ith element of the vector x and the k = (k 1 , k 2 ) element of the matrix X are given by x i and X k , respectively. | · | denotes cardinality of sets, absolute value for scalars and element-wise absolute value for vectors and matrices, also z ∞ = max i |z i |. For a function f and a matrix A, f ∞ , A ∞ , A and A 1 are defined as sup t |f (t)|, sup Az 2 and i,j |A(i, j)|, respectively. relint(C) denotes relative interior of a set C. ∂f (·)(x) denotes sub-differential of function f at point x. f i (t) and f i1i2 (t) denote ith derivate and i 1 , i 2 partial derivatives of one-dimensional function f (t) and two-dimensional function f (t := (t 1 , t 2 )), respectively. (·) T and (·) * show transpose and hermitian of a vector, respectively. sgn(x) denotes the element-wise sign of the vector x. Also, vec(X) denotes the columns of X being stacked on top of each other. The inner product between two functions f and g is defined as f, g := f (t)g(t)dt and ·, · denotes the real part of Frobenius product. ⊗ is Kronecker product and the adjoint of a linear operator F is denoted by F * .

II. PROBLEM FORMULATION
In the spectral domain the signal in (1) is a linear combination of Dirac delta functions: where T is support of the signal and δ(f − f i ) denotes the Dirac delta function located in f i . The main goal in LSE is to recover the location and amplitude of each delta by finite time samples. As mentioned in the introduction, many practical applications such as radar and sonar suffer from spiky noise due to their electrical instruments, so we going to investigate the two-dimensional LSE when a subset of time samples is completely corrupted by spiky noise. Assume that spiky noise is added to the signal (1) as: where Z k is an element of the sparse two-dimensional noise matrix Z ∈ C n×n with s non-zero entries. The observation model can be written in the matrix form: where F (·) is a linear operator that maps a continuous-indexed function in the frequency domain to two-dimensional integer square N in time domain. The problem is to simultaneously estimate the spectral sources and the location of spiky noise form Y .

III. ROBUST TOTAL VARIATION MINIMIZATION
The spectral sparsity is not sufficient to tackle this problem. In fact, if sources are located too close to each other,it would be impossible to resolve them [11].
Definition 3.1: Let T 2 be two-dimensional torus obtained by identifying the endpoints on [0, 1] 2 . For each set of points T ⊂ T 2 , the minimum separation is defined as: where |t 1i − t 1j |, |t 2i − t 2j | denote wrap-around distances on the unit circle.
1 minimization is not suitable for LSE problem, due to the discretization of spectral domain. Whereas, TV norm can promote the sparsity of continuous functions and defined as ν TV := sup ρ E∈ρ |ν(E)|. Indeed, TV norm maximizes the disjoint sum of positive measures |ν(·)| over all partitions ρ of square [0, 1] 2 . In the special case of (2), µ TV = r i=1 |c i |.
Most inverse problems are solved by minimizing a cost function that promotes an inherent structure [28]. This concept emerges in compressed sensing [6] and matrix completion [29]. The cost function may also include a specific penalty term to perform side tasks. For instance, [30] has shown that penalizing 1 norm with an 2 error term is an efficient way for denoising. The observation model (4) is sum of two sparse signals in different domains. [20] balances the TV norm of spectral sources and the 1 norm of spiky noise for one-dimensional case. We generalize this approach to twodimensional case by introducing the following optimization problem: where λ > 0 is a regularization parameter that makes a trade-off between TV norm of spectral spikes and 1 norm of spiky noise. The first goal of this paper is to prove that P TN achieves exact recovery and the second is to provide a valid semidefinite programming to solve this problem. The following theorem states that the solution of P TN is exact, under specific conditions. Theorem 3.1: Let J = {1, · · · , n} × {1, · · · , n} be the set of observed entries in the matrix, where each element of the noise matrix is independently nonzero with probability s n 2 supported on Ω (|Ω| = s). Also, the support of obeys where f i ∈ [0, 1] 2 and |T | = r. If r + s ≤ n 2 , then, the exact solution of P TN is (µ, Z) with probability 1 − for any > 0 and numerical constants C r and C s . Using Theorem 3.1 one can estimate the spectral sources and spiky noise samples up to logarithmic functions of the number of time samples under a mild condition on the separation of the spectral sources.

IV. CONSTRUCTION OF THE DUAL CERTIFICATE
The following proposition justifies that if there exists a low-pass trigonometric polynomial with coefficients in relative interior of sub-differential of 1 norm which interpolates any signal sign pattern in T , then it is a sufficient certificate for Theorem 3.1.
Proposition 4.1: If the conditions of Theorem 3.1 hold, for any sign patterns h ∈ C |T | and r ∈ C |Ω| such that |h i | = 1 and |r l | = 1, for all i and l, then there exists two-dimensional low-pass trigonometric polynomial such that where f i = (f 1i , f 2i ) and k l = (k 1l , k 2l ). (11) and (12) state that Q(f ) ∈ relint(∂( · TV (µ))), so for any measureμ Similarly, it can be deduced from (13) and (14) that C λ ∈ relint(∂( · 1 (µ))), so for anyẐ we have Letμ = µ +μ andZ = Z +Ẑ as a feasible point such that Y = F 2Dμ +Z: Proposition 4.1 guarantees existence and uniqueness of the solution (µ, Z). The following section shows that the coefficient of Q(f ) can be obtained by solving the dual problem of P TN .

V. THE DUAL PROBLEM
The main goal of this section is to suggest a positive semidefinite programming that estimates the location of the frequency sources and the spiky noise. More precisely, we want to convert the infinite dimensional P TN into a tractable problem. At the first step, the dual problem of P TN can be written using Lagrangian theorem. Then, the results of the PTP theory are applied to convert the explicit constraint of the dual problem into LMI.
Lemma 5.1: (Proof in Section XV-E ). The dual problem of P TN is given by where C is the dual variable. Due to establishment of Slater's condition, there is no gap between the objective value of dual and primal problems [31]. Therefore: Fig. 1: 1(a) shows the magnitude of the dual polynomial corresponding the dual solution of (20). Also, the support of spectral point sources and estimated sources are represented by blue and red lines, respectively.1(b) demonstrates the magnitude of dual solution of (20) in blue line and the support of spiky noise in red star. Consequently, |F * Ĉ | = 1 and |Ĉ k | = λ if f ∈ T and k ∈ Ω, respectively. this provides a strategy to recover the support of spectral sources and spiky noise (see Fig 1). The magnitude of the trigonometric polynomial can be controlled by LMI using the results of PTP theory [24]. Therefore, one can reformulate the dual problem to positive semidefinite programing as below: where Q 0 ∈ C n 2 ×n 2 is a Hermitian matrix that Q 0 0, Θ k = Θ k2 ⊗ Θ k1 , Θ k ∈ C n×n is an elementary Toeplitz matrix with ones on it's k-th diagonal and zeros else where, δ 0 = 1 and δ k = 0 if k = 0. In the next section we present numerical experiments to justify (20).

VI. EXPERIMENT
In this section we present numerical experiments for the observation signal (4) to investigate the performance of proposed positive semidefint programing (20). At the first experiment, we randomly generate r = 7 frequency sources in [0, 1] 2 without any separation condition, s = 7 spiky noises in {1, · · · , n}×{1, · · · , n} and also the coefficients of each sinusoidal is generated with random magnitude form δ 0.5 + X 2 (1) and random phase form U(0, 2π). We implement (20) using CVX [32] and leverage the mentioned technique in section V to recover the support of frequency sources and spiky noise. Fig. 1 demonstrates that local extremums of |F * Ĉ | that achieve one and the locations ofĈ that achieve λ are associated with inherent frequencies of (1) and locations of spiky noises.
In the second experiment, we investigate the phase transition of proposed approach for different amounts of the regularization parameter λ, under the fix minimum separation condition 3 n−1 . Indeed, we vary the regularization parameter when varying k and s (Fig. 2). As mentioned, λ makes a balance between the sparsity of two different components. Small λ more strongly penalizes TV norm of spectral spikes than 1 norm of spiky noise. This leads to a cost function which is more appropriate to promote the time domain sparsity and vice versa. Fig. 2 verifies the claim when we change λ from small to large values. First and second rows in Fig. 2 are receptively related to different numbers of measurements n 2 = 64 and n 2 = 81. The estimation is considered successful if the normalized mean squared error X −X 2 / X 2 ≤ 10 −3 , whereX andX are associated with X and reconstructed data when we omit the corresponding indices of spiky noise, respectively. Grayscale images show the empirical rate of success and each point of those are related to (k, s, n 2 ).

VII. CONCLUSION
In this work we investigate two-dimensional LSE problem, when a subset of time domain samples is corrupted by spiky noise. In addition, we proposed a semidefinite programming that achieves the exact solution under mild conditions on the number of spiky noise and the number and separation of spectral sources. One can extend our approach to arbitrary dimensions which is fundamental concern of many applications such as MIMO radar [1]. It is also worth mentioning that one could consider the model (3) in compressed sensing regime, namely, in case a random subset of time samples is only observed.

A. Deterministic Certificate
Without loss of generality, Assume that J = {−m, · · · , m} × {−m, · · · m} where m = n−1 2 and m = n 2 − 1 if n is odd or even, respectively. For dual certificate construction, consider the LSE problem in the noiseless case. [11] has shown that the following polynomial can estimate the frequency sources under a mild condition on their separations:Q such thatQ To ensure that |Q(f )| < 1 in the off-support, we follow the same approach in [11] and [13] to construct a deterministic dual certificatē whereᾱ,β 1 andβ 2 are interpolation vectors. To meet (22) and (23), the following conditions are sufficient [13] suggestedK for construction, in which where K(m, f ) = 1 2m+1 m k=−m e j2πkf is known as Dirichlet kernel, γ 1 = 0.247, γ 2 = 0.339, γ 3 = 0.414, and c ∈ C n is the convolution of the Fourier coefficients of k(γ 1 m, f ), k(γ 2 m, f ), and k(γ 3 m, f ). (25) and (26) can be reformulated as a matrix equation . We borrow two bounds on c ∞ and κ form [12] which are useful in advancing our proof

B. Random Certificate
Spiky noise randomly corrupts a subset of time samples, it is similar to random sampling in compressed sensing literature [14]. [20] uses the same technique to incorporate the randomness of spiky noise into dual certificate construction. We follow this approach to construct a valid certificate for two-dimensional case when a subset of time samples dose not follow the exponential structure. First, Q(f ) is divided into two terms where The coefficients of the first term are restricted to Ω c and the coefficients of the second term are in Ω. From the definitions, it is obvious that (13) is satisfied and R(f ) has no degree of freedom. So, we construct Q aux (f ) to guarantee other conditions in proposition 4.1. The inequality |Q(f )| ≤ 1, ∀f i ∈ T is satisfied by setting to zero the partial derivatives at T . So Define a restricted version ofK on Ω c where δ Ω c (k) = 1 if k = Ω c , δ Ω c (k) = 0 otherwise. Under the noise condition of Theorem 3.1, these are independent Bernoulli random variables with parameter n 2 −s n 2 . So the expectation of K(f ) can be written as: The mean of partial derivatives of K(f ) can be obtained by the same technique. we construct Q aux by a linear combination of K(f ) and its partial derivatives: where α, β 1 and β 2 ∈ C |T | are interpolation coefficient vectors. (35) and (36) can be recast in matrix form as follows where √ n 2 B Ω r can be written versus the components of R(f ) and their partial derivatives where k i1 , · · · , k is are associated with k ∈ Ω. Interpolation vectors can be computed by solving the linear system (40), so where The following Lemma establishes an upper bound on the 2 norm of b(k).
The following lemma establishes an upper bound on the operator norm of B Ω with certain probability. Lemma 8.2: (proof in section IX). If the conditions of Theorem 3.1 hold, the event happens with probability 5 in which numerical constant C B is defined in (127).
The following lemma sates that w i1i2 (f ) is concentrated around the scales version of on a fine grid with high probability.

C. Proof of Proposition 4.1
In the first step, we seek to determine the uniqueness of the solution of linear system (40). The following lemma shows that E is concentrated aroundĒ with high probability. Consequently, E is invertible and one can bound the operator norm of its inverse.
happens with probability /5. Also, under the event ε c E , E is invertible and where C D is the numerical constant which is defined by (134). Indeed, this Lemma states that, under the event ε c D , the linear system (40) has an stable solution. So Q(f ) is well defined and (11) holds. In order to meet (12), it is sufficient to show that Q(f ) is concentrated aroundQ(f ) on a fine gird. After that, using Bernstein's inequality, we demonstrate that this holds on the whole [0, 1] 2 . Finally we borrow some bound onQ(f ) and its partial derivative from [13] to complete the proof. Lemma 8.5: (Proof in section XV). If the conditions of theorem 3.1 hold, then with probability 1 − /5 under the event ε c B ∩ ε c E ∩ ε c v . The last to show is (14). The following lemma states that under the event ε c B ∩ ε c E ∩ ε c v , one can control the magnitude of dual polynomial's coefficients with high probability. Lemma 8.6: (Proof in section XV-D). If the conditions of Theorem 3.1 hold, then under the event ε c B ∩ ε c D ∩ ε c v . Finally, we use the same technique in [20] to complete the proof. Consider ε Q and ε q as the events, such that (12) and (14) hold, respectively. By De Morgan's laws and union bound we have In order to obtain an upper bound on the operator norm of B Ω , under the assumption of theorem 3.1, we show that is concentrated around Using the following lemma, we can compute an upper bound on the operator norm ofH.
Regarding the fact that s ≤ C s n 2 log 2 k log n 2 −1 in Theorem 3.1 we have s n 2H ≤ if we set C B small enough. One can demonstrate that H concentrates around the scaled version ofH using matrix Bernstein inequality.
which happens with probability at least 1 − /5.
X. PROOF OF LEMMA 9.1 Consider two-dimensional Dirichlet kernel whereK m (f ) := 1 n k∈{−m,...,m} e j2πf k is known as Dirichlet kernel.H can be recast in matrix form usingK(f ) as A uniform bound on the magnitude of the Dirichlet kernel is obtained by Bernstein's polynomial inequality in [12] |K m (f )| ≤ (2m) .
So we can uniformly bound the magnitude ofK(f ) and its partial derivatives using this bound and (61) There is another bound on the magnitude of Dirichlet kernel and its derivatives which holds for m ≥ 10 3 and f ≥ 80/m (See section C.4 for proof). Similar to (61), we have for the domain in which min(|f 1 |, |f 2 |) ≥ 80/m. These bounds can be used for bounding sum of magnitudes ofK(f ) and its partial derivatives. Assume that f i ∈ T is fixed. There are at most 95 2 other frequency sources that are in square f − f i ∞ ≤ 80/m with respected to the minimum 3.36 m . Now we are able to bound those terms as below for k ≥ 2 and i 1 , i 2 ∈ {0, 1, 2, 3}. The last inequality is obtained by ∆ min = 1.68/m, (31), and the fact that 9025 + 108 log 2 k ≤ 74569 log 2 k. It is possible to bound the eigenvalue ofH using Gershogrin's disk theorem which leads to a bound on the operator norm of H.
This concludes the proof.
XI. PROOF OF LEMMA 9.2 Lemma 11.1: (Bernstein's matrix inequality [33]). Let X(1), · · · , X(L) be independent zero-mean self-adjoint ran- for any t ≥ 0 and σ 2 := L k=1 E X(k)X T (k) . Consider a finite sequence of independent adjoint zero-mean random matrices of the form The aim is to show that H concentrates around s n 2H with high probability. We can write One can bound the operator norm of X by Lemma 8.1 Also, where the last inequality comes from (58), the second from Lemma 8.1 and the first stems from the variance of Bernoulli model with parameter s n 2 . Assume t := C 2 B n 2 2 log n 2 −1 in Lemma 11.1 for simplicity, so σ 2 := 21rt. We can write The lower bound of the probability is equal to /5 under the condition This criterion is satisfied by setting C r in Theorem 3.1 small enough.
XII. PROOF LEMMA 8.3 Lemma 12.1: (Vector Bernstein's inequality [34]). Let u(1), · · · , u(L) be independent zero-mean random vectors of dimension d. If u(k) 2 ≤ B ∀k, we have where δ Ω c is iid Bernoulli random variable with parameter p := n 2 −s n 2 . We apply the result of the vector Bernstein inequality in Lemma 12.1 to the finite sequence of zero-mean random vectors of the form to demonstrate that the deviation between w i1i2 (f ) and the scaled version ofw i1i2 (f ) is small enough with high probability for i 1 , i 2 ∈ {0, 1, 2, 3}. We can write To calculate B in Lemma 12.1, one can obtain an upper bound on 2 norm of u where the last inequality comes from (31) and (30), and i 1 = i 2 = 3. Also, To compute σ 2 in Lemma 12.1 we have where the first inequality is obtained from Lemma (8.1), (31), and the fact that variance of Bernoulli model is equal to p(1 − p) ≤ 1. The second inequality comes from (30) for i 1 = i 2 = 3. By leveraging the result of the vector Bernstein inequality in Lemma 12.1, we have by union bound. The lower bound of probability is equal to /5, if we set t as In the following, we show that this choice of t satisfies 0 ≤ t ≤ σ 2 B , t σ = 8( 1 4 + log 45|G| ) ≤ 86 + 32 log n + 8 log 1 where the last inequality comes from the fact that √ 86 + 32 log n ≤ n for n ≥ 13, consequently, t ≤ σ 2 B if we set C r and C s small enough in Theorem 3.1. The desired result is obtained for 768 × 10 7 r n 2 if we set C r small enough in Theorem 3.1.
XIII. PROOF OF LEMMA 8.4 The proof involves the same techniques which were first proposed in [14]. In the following Lemma, we demonstrate that the matrixĒ is similar to the identity matrix and consequently is invertible.
Lemma 13.1: (Proof in section XIV). If the conditions of Theorem 3.1 hold, then It is possible to writeĒ and E in terms of the matrix bb * . By the definition ofK 2D and K 2D , we havē One can show that E is concentrated around n 2 −s n 2Ē with high probability. We first define the self-adjoint zero mean matrix X as below where One can bound the the operator norm of X using Lemma 8.1 and the upper bound on the maximum of the vector c Also, where the first inequality uses the variance of the Bernoulli model with parameter p and Lemma 8.1, the second stems from (30) and the definition ofĒ and the last one is the result of Lemma 13.1. We set t = p 4 C min log n 2 − 1 2 where C min := min{1, C D 4 } for simplicity. By matrix Bernstein inequality (Lemma 11.1), we can write for numerical constant C D . The lower bound on this probability is /5 under the conditions which hold under the assumption of Theorem 3.1, if we set C r and C s small enough.
Consequently, the lower bound on the smallest singular value of E can be obtained by triangle inequality, Therefore, E is invertible. [14, Appendix E] states that for any matrices A and B so that B is invertible and A − B B −1 ≤ 1 2 one can write Consider A := E and B := pĒ. Using Lemma (13.1) and (94), we have with probability at least 1 − /5. Based on this and Lemma 13.1, and event (94) we also have with the same probability. Regarding the conditions of Theorem 3.1 s ≤ n 2 2 , therefore 1 p ≤ 2. This concludes the proof.
XIV. PROOF OF LEMMA 13.1 We borrow some bound on the sub-matrices ofĒ from [13] under the minimum separation condition where the inequalities are obtained by (31). Gershgorin's disk theorem allows to bound the operator norm of the matrix I −Ē where the last inequality comes from (31) and the results of the Lemma 14.1. Consequently, and also, XV. PROOF OF LEMMA 8.5 It is possible to express Q i1i2 (f ) andQ i1i2 (f ) in terms of h and r: Q i1i2 (f ) andQ i1i2 (f ) are related to each other as in which In the following Lemma, we show that there exists a bound on these terms on two-dimensional grid G with high probability.
Lemma 15.1: (Proof in section XV-A). If the conditions of Theorem 3.1 hold, then the events and for i ∈ {0, 1, 2, 3} and two-dimensional equispaced gird G with set size 800n 4 , happen with probability at most /5 under the condition ε c B ∩ ε c D ∩ ε c v . Consequently, by triangle inequality we have with probability at least 1 − /5 under the condition ε c B ∩ ε c D ∩ ε c v . We have already shown that the deviation between Q i1i2 (f ) andQ i1i2 (f ) is small on a fine grid. Now we will extend this concept on the whole [0, 1] 2 .
Lemma 15.2: (Proof in section XV-C). If the conditions of Theorem 3.1 hold, then We divide [0, 1] 2 to two domains [13] has demonstrated that |Q(f )| ≤ 0.9866 for f ∈ S far . One can leverage the result of Lemma 15.2 and triangle inequality to obtain for f ∈ S far . Also, [13] has shown that the following Hessian matrix is More precisely,Q 20 ≤ −1.4809m 2 ,Q 02 ≤ −1.4809m 2 and |Q 11 | ≤ 1.4743m 2 . It is possible to rewrite the elements of the matrixH for Q(f ) then using the result of Lemma 15.2 by (31). If the matrix H is concave, then Q(f ) < 1. The sufficient condition for concavity of this matrix is Tr(H) < 0 and det(H) > 0, where By (117), it is easy to see that Tr(H) < 0 and det(H) > 0, so the Hessian matrix H is negative definite in the domain S near . This concludes the proof.
A. Proof of Lemma 15.1 We follow a technique first proposed in [20] to prove this lemma.
Lemma 15.3: (Hoeffdings Inequality [35]). If the elements ofũ are sampled independently and identically distributed from a symmetric distribution on the complex unit circle, then for any t and vector u one can write Consequently, the event where U is a finite collection of vectors with size 9|G| = 72 × 10 2 n 4 , happens with probability at most /20 under the condition The proof follows from the union bound and the fact that log 576×10 2 n 4 −1 < log n 2 −1 .
, one can use the following vector in which f belongs to G, so that |U| = 9|G| and also κ i1+i2 R i1i2 (f ) = r, u i1i2 (f ) . In the following, we show that u i1i2 (f ) 2 satisfy the criterion of Lemma 15.3 where the first inequality stems from the union bound, the second one from (31), and the last one is obtained if we set C s small enough in the conditions of Theorem 3.1.
One can obtain a bound on u i1i2 (f ) 2 using a bound on w i1i2 (f ) 2 2 and Lemma 8.3. The following Lemma provides a bound on 2 norm of w i1i2 (f ) Lemma 15.4: (Proof in section XV-B). If the conditions of Theorem 3.1 hold, then where Cv is a fixed numerical constant. Consequently, where we have used ε c v in Lemma 8.3 and triangle inequality and the facts that n 2 −s n 2 ≤ 1 and log n 2 − 1 2 ≤ 1. Combining this and the result of Lemma 94, under the condition ε c D ∩ ε c v . If where P ∈ R r×3r is a projection matrix that takes the first r entries in a vector. One can obtain an upper bound on 2 norm of u i1i2 (f ) using Lemma 94 in ε c D as follow where the last inequality comes from the fact that P = 1 and it is valid for f ∈ G, so that |U| = 9|G|. If Then the desired bound in Lemma 15.3 is achieved for the numerical constant C v . The condition on the deviation of w i1i2 (f ) and n 2 −s n 2 w i1i2 (f ) holds with respected to ε c v in Lemma 8.3.
Finally, we bound P( One can bound 2 norm of u i1i2 (f ) ∀f ∈ G for i 1 , i 2 ∈ {0, 1, 2, 3}, so |U| = 9|G| where the last inequality comes from Lemma 15.4 and P = 1. If Regarding the fact that · 2 ≤ · 1 , we have We first borrow the result of Lemma H.10 from [12] to bound the magnitude of two-dimensional kernel in unit square Lemma 15.5: ( [12, Lemma H.10]) where C 1 and C 2 are numerical constants.
for i 1 , i 2 ∈ {0, 1, 2, 3}, where C 1 and C 2 are numerical constants defined in Lemma 15.5. The minimum separation condition implies that there exist at most 95 2 support elements in the square f − f i ∞ ≤ 80 m . We bound those elements by C 2 1 and use the decreasing bound to handle the remaining components We first use the bound on the deviation between Q i (f ) and Q i (f ) from [12] for any f 1 , f 2 ∈ [0, 1] and i ∈ {0, 1, 2, 3}. Also, consider another useful bound κ i |K(f )| ≤ Cn 2 where C is a numerical constant. One can extend this concept to two-dimensional case using Bernstein's polynomial inequality as below, (140) [15] has done a similar analysis in the proof of Lemma 7.
For any f ∈ [0, 1] 2 there exists two-dimensional grid point f G such that the maximum distances between two points is smaller than the step size (800C 2 n 4 ) −1 . So, Lemma 15.1 and triangle inequality lead to And the proof is complete.
D. Proof of Lemma 8.6 One can recast the coefficient C k in terms of h and r. Let k be an arbitrary element of Ω c where P ∈ R r×3r is the projection matrix that retains the first r entries of a vector.
To bound |C k |, we first obtain a bound on P E −1 b as below where the last inequality is obtained under the conditions of Theorem 3.1 when we set C k small enough and the second one is a combination of Lemmas 8.1 , 8.4 and the fact that P 2 = 1. Also, we have where the second inequality stems from Lemmas 8.1 and 8.2 and the last one comes from the assumption of Theorem 3.1 if we set C r small enough.
One can obtain /10 for the minimum probability of the following events by Hoeffding's inequality Using c ∞ ≤ 1.3 m and the union bound, we have |C k | ≤ 2.6 2 n 2 0.07 √ n 2 + 0.07 with probability at least 1 − /5. This concludes the proof.
E. Proof of Lemma 5.1 Consider C ∈ C n×n as the dual variable. By Lagrangian theorem we have One can minimize this function with respect toμ andZ simultaneously, then maximize over dual variable C [31]. At the first. by Holder's inequality, we have If F * C ∞ ≤ 1 and C ∞ ≤ λ, then the minimum occurs at C, Y otherwise, the problem is unbounded below. For second, we should maximize this term on C as below Converting the implicit conditions into explicit conditions concludes the proof.