{'fraction_non_alphanumeric': 0.03958233547274643, 'fraction_numerical': 0.012664048280486636, 'mean_word_length': 4.422961038961039, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 0, '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}}
Sensing Matrix Design and Sparse Recovery on the Sphere and the Rotation Group

In this paper, {the goal is to design deterministic sampling patterns on the sphere and the rotation group} and, thereby, construct sensing matrices for sparse recovery of band-limited functions. It is first shown that random sensing matrices, which consists of random samples of Wigner D-functions, satisfy the Restricted Isometry Property (RIP) with proper preconditioning and can be used for sparse recovery on the rotation group. The mutual coherence, however, is used to assess the performance of deterministic and regular sensing matrices. We show that many of widely used regular sampling patterns yield sensing matrices with the worst possible mutual coherence, and therefore are undesirable for sparse recovery. Using tools from angular momentum analysis in quantum mechanics, we provide a new expression for the mutual coherence, which encourages the use of regular elevation samples. We construct low coherence deterministic matrices by fixing the regular samples on the elevation and minimizing the mutual coherence over the azimuth-polarization choice. It is shown that once the elevation sampling is fixed, the mutual coherence has a lower bound that depends only on the elevation samples. This lower bound, however, can be achieved for spherical harmonics, which leads to new sensing matrices with better coherence than other representative regular sampling patterns. This is reflected as well in our numerical experiments where our proposed sampling patterns perfectly match the phase transition of random sampling patterns.


Introduction
In many applications, where the goal is to recover a sparse signal from the fewest linear measurements, the measurement process cannot be freely chosen. That is, in the corresponding linear inverse problem, the sensing matrix has a specific structure. A central question, therefore, is to design the sensing matrix under these additional restrictions.
For general sensing matrices, the pioneering works of compressed sensing [1][2][3] followed by overwhelming subsequent researches established recovery guarantees for various random matrices including subgaussian random matrices. These random matrices are shown to satisfy, with high probability, the Restricted Isometry Property (RIP), which is a sufficient condition for noise-robust sparse recovery. Many efficient algorithms such as Basis Pursuit (BP) can provably recover the original signal from these measurements (see [4] for an exhaustive treatment of the subject).
In contrast to pure random matrix designs, in many applications, the sensing medium imposes additional structures on sensing matrices. Notable examples are sensing matrices is equal to B 2 , which implies that K = (2 √ N − 1)/4π. When this is plugged in the recovery guarantees for BOSs, it would imply that the number of measurements should scale badly with the dimension N . This bound is useless for sparse recovery analysis. Rauhut and Ward used a preconditioning technique in [9] and improved the dependence to N 1/4 . Burq et al. improved this further to N 1/6 in [10]. These results, however, do not directly generalize to Wigner D-functions.
As soon as we move to deterministic sampling patterns, the RIP cannot be used to appraise the sparse recovery capability of the sensing matrices. It is computationally hard to certify that a certain matrix satisfies RIP [15,16]. A common metric for deterministic sensing matrices is the mutual coherence. It is defined as the maximum of the absolute value of normalized inner products between columns of the sensing matrix. Unlike RIP, the mutual coherence can be numerically evaluated for a given matrix, and therefore it is a computable figure of merit for sparse recovery. The mutual coherence of a matrix can also be used to provide recovery guarantees, although it leads to a suboptimal dependence on the sparsity order. In general, sensing matrices with low mutual coherence tend to have better sparse recovery performance. Therefore, constructing a sensing matrix with low mutual coherence has been widely investigated in recent years because of its extensive application in many different areas, from coding theory and communication [17,18], compressed sensing [2,3,[19][20][21], quantum measurement [22], and machine learning [23,24]. The mutual coherence is lower bounded by the Welch bound, obtained in the context of correlation measurements of different signals [25]. The lower bound is tight and can be achieved by equiangular and tight frames [17]. A similar result for structured matrices is not known to the best of our knowledge.

Related Works
Deterministic sampling patterns on the sphere S 2 have been studied extensively in the context of Shannon-Nyquist sampling for the reconstruction of band-limited functions (see [26][27][28] and references therein). As mentioned by McEwen and Wiaux in [26], some of these techniques can be used to enhance the performance of compressed sensing methods. Equiangular sampling patterns are often the standard in these applications. In these works, to represent a band-limited function with a bandwidth of B, the number of samples should scale as O(B 2 ), which is linear in the ambient dimension. For high bandwidth signals, it implies a long measurement time. Compressed sensing approach can circumvent this issue by leveraging the sparsity structure in the signal. We will see, however, that equiangular sampling patterns are not good choices for compressed sensing.
Compressed Sensing (CS) over sphere has been considered in a few works. Deterministic sensing matrix design from spherical harmonics was considered in [29] where spiral sampling points are used as the basis for the design. They show that the proposed sampling points outperform equiangular sampling. However, those works emphasize numerical evaluations of the sparse recovery without analyzing the structure of sensing matrices, discussing the achievable coherence bounds or providing design guidelines. The authors in [30] considered probabilistic CS to provide recovery guarantees without using RIP. Relying on preconditioning approaches of [10], the approach provided a probabilistic recovery guarantees for which the number of measurements depends on N 1/6 for spherical harmonics. These results usually rely on some conditions on the sensing matrix (see [4,Chapter 14]). Besides, the result does not hold uniformly over all vectors. In many applications, it is difficult to conduct measurements using random sampling patterns. To the best of our knowledge, this work is the first to consider functions over the rotation group and provide mutual coherence-based guidelines for designing deterministic sensing matrices of spherical harmonics and Wigner D-functions.

Summary of Contributions
In this paper, we consider the problem of sensing matrix design and evaluation for sparse recovery of band-limited functions on the sphere S 2 and the rotation group SO(3). Although there are some works on sensing matrix design over the sphere, the problem is almost unexplored for the rotation group. One of the main contributions of this paper is to study sensing matrix design for compressed sensing over the rotation group. The sensing matrix design boils down to finding m sampling points (θ, φ) ∈ S 2 and (θ, φ, χ) ∈ SO(3), where θ ∈ [0, π], φ ∈ [0, 2π) and χ ∈ [0, 2π). For spherical harmonics, certain random sampling patterns can be provably used for sparse recovery [7]. In Section 3, we prove that it is also possible to find a pair of points on the rotation group with guaranteed sparse recovery. Specifically, sparse band-limited signals over the rotation group SO(3) can be uniquely recovered from certain random sampling patterns by solving a convex optimization problem. The proof follows from the RIP property of the sensing matrix after preconditioning, which is based on some inequalities for Jacobi polynomials. The required number of samples scale with the ambient dimension as N 1/6 . The recovery algorithm is robust to noise and stable to model inaccuracies. These results show that it is possible to find sampling patterns with recovery guarantees on the sphere and the rotation group. The focus of our paper, however, is on deterministic sampling pattern design. This paper discusses for the first time compressed sensing over the rotation group. We provide new tools, guidelines and designs for the problem of deterministic sensing matrix design over the sphere and the rotation group. The main contributions of our paper are as follows.
• Adopting the mutual coherence as the figure of merit from Section 4, we show that certain regular deterministic sampling patterns over the sphere and the rotation group with symmetric structures over φ and χ have maximum coherence and, therefore, are not good for sparse recovery. These patterns include many of sampling patterns that are currently widely used in applications, including equiangular sampling patterns.
• The mutual coherence is determined by the inner products of vectors of samples of spherical harmonics and Wigner D-functions. We show in Section 4 that the product of two functions can be seen as the total angular momentum of a composite quantum system. Borrowing this insight from quantum mechanics, the product can be decomposed into a sum of single spherical harmonics and Wigner D-functions using Wigner 3j symbols. To the best of our knowledge, this decomposition is used for the first time for coherence analysis in compressed sensing. We use the above decomposition to derive regular sampling patterns that lead to mutually orthogonal, and therefore incoherent, columns in the sensing matrix.
• In Section 5, we propose equispaced sampling patterns on θ, which also leads to incoherent columns. We show that once the sampling points on θ is fixed the mutual coherence is automatically lower bounded independent of the choice of φ's and χ's. It is, however, shown that the lower bound can be achieved for spherical harmonics with our newly proposed sampling pattern. The new sampling pattern is obtained by an algorithm that minimizes the mutual coherence using pattern search algorithm. Although the lower bound cannot be achieved for Wigner D-functions using this method, the mutual coherence of our proposed pattern is still superior to the representative regular sampling patterns.
• Our phase transition diagrams in Section 6 suggest that our proposed sampling pattern not only outperforms the representative regular patterns but also matches perfectly random sampling patterns. We demonstrate the benefit of our sampling pattern in some potential applications. These applications include spherical nearfield antenna measurements as well as the reconstruction of the earth's magnetic field. We show that, for both cases the required number of samples can be significantly reduced.
The codes used in this paper are available below: github.com/bangunarya/samplingsphere

Notation
The vectors are denoted by bold small-cap letters. Define N := {1, 2, . . . } and N 0 := N ∪ {0}. Throughout the paper, a b means that there is a universal constant C such that a ≤ Cb. Similar convention is used for a b. f (x) for a function f : R → R is the element-wise application of f to the vector x.
x is the conjugate of x.

Definitions and Backgrounds
In this section, we introduce briefly the preliminaries of signal processing over the sphere and the rotation group as well as the problem formulation. The central problem of this work is the recovery of band-limited functions defined on the sphere and the rotation group. We need, therefore, to introduce Fourier analysis for these spaces of functions.

Spherical Harmonics and Wigner D-functions
Consider the Hilbert space of square-integrable functions f (·) on the sphere S 2 denoted by L 2 (S 2 ). Each element of S 2 is represented by two numbers θ ∈ [0, π] and φ ∈ [0, 2π). The variables θ and φ are called the elevation and the azimuth. The inner product of f, g ∈ L 2 (S 2 ) is defined by where dν(θ, φ) := sin θdθdφ is the uniform measure on the sphere. Spherical harmonics are basis functions for the space of functions in L 2 (S 2 ). Denoted by Y k l (θ, φ) for degree l ∈ N 0 and order k ∈ {−l, . . . , l}, they are defined over the sphere S 2 as follows: where P k l (cos θ) is the associated Legendre polynomials defined by The term N k l := 2l+1 4π (l−k)! (l+k)! is a normalization factor. It ensures that the function Y k l has unit L 2 -norm. Spherical harmonics are orthonormal with respect to the uniform measure on the sphere dν = sin θdθdφ, i.e., where δ ll is the Kronecker delta. The function Y k l is the conjugate of Y k l and satisfies: For any function f ∈ L 2 (S 2 ), the unique expansion is called the S 2 -Fourier expansion of f with Fourier coefficientsf k l . The space of all rotations of the sphere S 2 is a group called the rotation group and is denoted by SO (3). Each element of SO(3) can be represented by three rotation angles φ ∈ [0, 2π), θ ∈ [0, π], and χ ∈ [0, 2π). In this work, we call the angle χ the polarization. The Hilbert space of square integrable functions on SO(3), denoted by L 2 (SO(3)), is endowed with an inner product, which is defined for two functions f, g ∈ SO(3) by where dν(θ, φ, χ) := sin θdθdφdχ. Wigner D-functions are an orthonormal basis for the Hilbert space L 2 (SO(3)). Denoted by D k,n l (θ, φ, χ) with degree l ∈ N 0 and orders k, n ∈ {−l, . . . , l}, they are defined by where N l = 2l+1 8π 2 is the normalization factor to guarantee that Wigner D-functions are unit norm. The function d k,n l (cos θ) is the Wigner d-function of oder l and degrees k, n defined by: where γ = α!(α+ξ+λ)! (α+ξ)!(α+λ)! , ξ = |k − n|, λ = |k + n|, α = l − ξ+λ The function P (ξ,λ) α is the Jacobi polynomial defined by The orthonormal property of Wigner D-functions writes as: The conjugate of D k,n with Fourier coefficientsĝ k,n l are obtained bŷ g k,n l = 2π 0 2π 0 π 0 g(θ, φ, χ) D k,n l (θ, φ, χ) sin θdθdφdχ.
An interested reader can refer to the book [32] for more information on Wigner Dfunctions and SO(3).
Remark 1. If the order n is set to zero, we get spherical harmonics. The Wigner Dfunctions D k,0 l for n = 0 are related to spherical harmonics Y k l as

Sparse Expansions of Band-limited Functions
In this work, we are interested in band-limited functions inside L 2 (S 2 ). A function f ∈ L 2 (S 2 ) is band-limited with bandwidth B if it is expressed in terms of spherical harmonics of degree less than B: The space of band-limited functions with the degree less than B is a subspace of L 2 (S 2 ) of dimension N = B 2 . Every band-limited function f , therefore, is fully determined by the vector of N Fourier coefficients f = (f k l ) 0≤l<B . We can define similarly the notion of band-limited functions on SO(3). A function g ∈ L 2 (SO (3) The space of band-limited functions with the degree less than B is a subspace of where each function is completely determined by the vector of Fourier coefficients, g = (ĝ k,n l ) 0≤l<B . A band-limited function, whether in L 2 (S 2 ) or in L 2 (SO(3)), is said to be s-sparse if the vector of its Fourier coefficient x, i.e., x = f or x = g, has at most s non-zero entries. This is stated in terms of the 0 -norm 1 as x 0 ≤ s. For the general non-sparse vector of coefficients x, either in L 2 (S 2 ) or in L 2 (SO(3)), the best s-sparse approximation error of x is defined by: In many applications, the signals are approximately sparse or compressible, that is, the s-sparse approximation error decreases rapidly as s increases. 1 The 0 -norm of a vector x ∈ C n is defined by: where 1(·) is the identity function. Needless to say that 0 -norm is called a norm just as a convention. It is, indeed, not a norm.

Linear Inverse Problems and the 1 -minimization
Consider a band-limited function either in S 2 or SO(3). The function belongs to a finitedimensional vector space and can be represented by its Fourier coefficients. It is therefore enough to find the Fourier coefficients, a finite-dimensional vector, to specify the function. We want to find the Fourier coefficients of a band-limited function from noisy linear samples of the function using as few samples as possible. We focus on SO(3), which contains S 2 as a special case. Consider a function g ∈ L 2 (SO (3)). We obtain m noisy samples y p of the function g at points (θ p , φ p , χ p ) for p ∈ [m]. The samples are given by: where η p is the additive noise with |η p | ≤ . The noisy samples are therefore linearly related to the coefficients g = (ĝ k,n l ) 0≤l<B as follows: where the sample and the noise vectors are given by: The noise vector satisfies η ∞ ≤ . The matrix A, called the measurement or sensing matrix, is given by: The columns of A consist of m different samples of Wigner D-functions, and its rows are comprised of a single sample of all Wigner D-functions of degree less than B. The ordering of Wigner D-functions in a row is arbitrary. The only caveat is that the vector g ∈ C N of N coefficients should be similarly ordered. For simplicity, we assumed that the degree and orders of the Wigner D-function in the column q ∈ [N ] are determined by three functions l(q), k(q) and n(q). In this way, the Wigner D-function of the column q is D . The entry q of g isĝ k(q),n(q) l(q) , and the matrix A is written as The linear inverse problem is similarly defined for spherical harmonics by removing the polarization parameter from the above equation. In both cases, we are interested in finding the Fourier coefficients from a few samples.
If the vector of coefficients g, or f , are sparse or compressible, there are many algorithms for finding the coefficients from a number of samples m that is smaller than the dimension N . In this paper, we use quadratically constrained basis pursuit, i.e., 1 -minimization problem to solve the problem (11). The focus, however, is more on different sampling patterns and their effectiveness for signal recovery. The quadratically constrained basis pursuit is defined below: In the next sections, we consider various sampling patterns and their recovery guarantees.

Sparse Recovery Guarantees for Random Matrices
How should the sensing matrix A be chosen for the program (QCBP) to find a good approximation of compressible coefficients vectors? The error of a good approximation is only bounded by the model and measurement inaccuracies determined by the s-sparse approximation error and the noise strength. Therefore, we are interested in choosing A such that any s-sparse vector can be perfectly recovered from noiseless linear measurements. This is shown to be possible in compressed sensing literature if the samples are taken randomly from a class of distributions. In most of these results, the proof amounts to showing Restricted Isometry Property, a sufficient condition for signal recovery, for the sensing matrix A. The RIP is defined below.

Definition 1.
A matrix A∈ C m×N satisfies the restricted isometry property of order s with constant δ ∈ (0, 1), if the following inequalities hold for all s-sparse vectors x∈ C N The smallest number δ, denoted by δ s , is called the restricted isometry constant of A.
Fortunately, a general result for BOSs is available. The result is used later, and we present it for the paper to be self-contained.
Theorem 1 (RIP for BOS [4,Theorem 12.31]). Consider a set of bounded orthonormal basis ψ q : D → C, q ∈ [N ] that are orthonormal with respect to a probability measure ν on the measurable space D. Consider the matrix ψ ∈ C m×N with entries then with probability at least 1 − N −γlog 3 (s) , the restricted isometry constant δ s of 1 √ m ψ satisfies δ s ≤ δ for δ ∈ (0, 1). The constants C, γ ≥ 0 are universal.
The crucial assumption, as we will see later, is the uniform boundedness of ψ q (·). Once the RIP property is satisfied by a matrix, s-sparse vectors are recovered perfectly using the program (QCBP). RIP property, indeed, implies the robust and stable null space property which is the necessary and sufficient condition for unique recovery (see [4,Chapter 12]). The following theorem summarizes this result.
Theorem 2 (Sparse Recovery for RIP Matrices [4,Corollary 12.34]). Suppose that the matrix ψ ∈ C m×N has restricted isometry constant δ 2s ≤ 0.4931. Suppose that the measurements are noisy y = ψx + η with η ∞ ≤ . If x # is the minimizer of where C depends only on δ 2s . Without noise, we have x = x # for s-sparse vectors x.
Unfortunately the results of Theorem 1 and 2 provide only weak bounds for spherical harmonics and Wigner D-functions, because these orthonormal functions are not uniformly bounded, as mentioned in [9]. More precisely, see that: The value of Y 0 l (0, φ) can be shown to be the upper bound on all spherical harmonics of degree l. This means that all spherical harmonics of degree less than B are bounded by 2B−1 4π , and the bound is tight. Since the ambient dimension N is equal to B 2 , the uniform upper bound K on spherical harmonics depends on N as K = O( √ B). Theorem 1, then, yields a bound on m that depends on the ambient dimension as O( √ N ). A more general dependence of this type appeared in the paper [10]. This dependence might yield vacuous bounds on the measurement numbers for large dimensions and very sparse vectors.
Rauhut and Ward in [9] and Burq et al. in [10] used a preconditioning technique that improves this dependence for spherical harmonics. At the core of the preconditioning technique lies the following inequality: Burq et al. [10] change the probability measure defined on S 2 to the measure dν = | tan θ| 1/3 dθdφ and preconditioned the spherical harmonics by (sin 2 θ cos θ) 1/6 . Note that further normalization by a constant is needed to turn the new measure to a probability measure. The new probability measure, however, improves the dependence of m on N to O(N 1/6 ), which improves also the previous precondtioning by (sin θ) 1/2 proposed in [9]. The upper bound on Wigner D-functions, similarly, depends on N . In particular, see from the equality 10, that the upper bound K is also O( , the measurement number m should depend on N as O(N 1/3 ). We propose a similar preconditioning technique to improve this bound. The following inequality is crucial for our derivations: We prove the above inequality in the appendix. This inequality suggests that the upper bound is improved if we precondition D k,n l by (sin θ) 1/2 . The preconditioning technique can be applied with Theorem 1 and Theorem 2 to yield the recovery guarantee for random sampling patterns, stated in the following theorem. Theorem 3. Consider the problem (11) of finding Fourier coefficients g of a band-limited function g ∈ L 2 (SO(3)) from noisy linear measurements y = Ag + η with η ∞ ≤ .
Suppose that the sensing matrix A is constructed as (12) using m i.i.d. samples . The number of measurements m is assumed to satisfy the following inequality Then with probability at least 1 − N −γlog 3 (s) , the following holds. If g # is the solution to the following problem then, In particular, when the measurements are not noisy, the recovery is unique for s-sparse signals, namely g = g # .
Proof. The proof is given in Appendix A.
Remark 2. The recovery guarantee proofs for many algorithms are based on RIP. Therefore our RIP proof implies recovery guarantee for algorithms like iterative hard thresholding, hard thresholding pursuit and orthogonal matching pursuit (see [4,Remark 12.35]).
Remark 3. The role of preconditioning matrix is to counter the increase of Wigner Dfunctions at the endpoints of the interval. As we discussed above, there is a more general result based on pre-conditioning given in [10]. Their results applies to the functions that are canonical solutions to Laplacian defined over a compact n-dimensional Riemannian manifold. Spherical harmonics and Wigner D-functions belong to this class of functions. It has been shown that the first N canonical solutions, called eigenfunctions, defined on a compact n-dimensional Riemannian manifold are uniformly bounded by N n−1/2n [10, Corollary 2]. For SO(3), a 3-dimensional compact manifold, this approach yields the bound N 1/3 which is worse than the result above. As stated in [10], this bound deteriorates as the dimension of underlying manifold increases. There is another more powerful result in [7,10] with better scaling with N . This result applies to functions defined over surfaces of revolution. However, Wigner D-functions are not defined for surfaces of revolution, and therefore these results do not apply. In the numerical results, we also consider the performance of preconditioning and measure in [10]. It is, however, not clear at the moment how a similar bound can be obtained for Wigner D-functions.
physical limitations for taking too close measurements. Therefore sampling patterns that are sufficiently distant and lead to smoother probe movements are preferred. In practice, the sampling points are chosen from some known structures like equiangular sampling patterns. The main challenge is to find suitable regular patterns for sparse recovery. Verifying RIP for deterministic sensing matrices is computationally hard. Furthermore, except the single example of [33], only randomly generated sensing matrices have been shown so far to satisfy RIP. There are, however, examples of matrices that do not satisfy RIP and yet provide provable recovery guarantees [34]. Therefore, instead of using RIP, we choose another notion to assess whether a sensing matrix is suitable for solving inverse problems. There are other concepts for evaluating the goodness of sensing matrices, such as spark or mutual coherence of a matrix. The mutual coherence has been used to construct deterministic sensing matrices. For Fourier basis, the authors in [35] used tools from combinatorial number theory, in this case difference sets, to construct deterministic partial Fourier matrices for specific choice of input dimension N and measurement numbers m. This construction was shown to achieve the Welch bound. When the input dimension N is prime and with specific m ≤ N , the authors in [36] developed a method to produce deterministic Fourier matrices that can recover sparse signals with for ∈ (0, 1). The authors in [37] proposed a construction that can recover sparse signal with sparsity dimension s < √ m 2(N −1) + 0.5 by using BP.
In contrast to Fourier sensing matrices, there are only limited works related to the construction of deterministic sensing matrices from spherical harmonics and Wigner Dfunctions for compressed sensing. For instance, spiral sampling points are used to construct such sensing matrices, as investigated in [38][39][40], and perform numerical comparison of success recovery several compressed sensing algorithms. To the best of our knowledge, this paper is the first work to discuss the coherence bounds for those matrices.
Definition 2. The mutual coherence of a matrix A = [a 1 . . . a N ] ∈ C m×N is defined as the maximum of the normalized inner product of columns of the matrix, i.e., The mutual coherence belongs to the interval [0, 1]. As a rule of thumb, the coherence of the sensing matrix should be very small for recovery of moderately sparse vectors. It is possible to obtain recovery guarantees for deterministic sensing matrices using its coherence value (for example see [4,Theorem 5.7]). These results, however, yield bounds on the number of measurements that scale quadratically with the sparsity level. This is underwhelming even for moderate sparsity regime. Nevertheless, the coherence can still be used as a good indication for fitness of a sensing matrix, which is the approach we opt in this article.
The mutual coherence expression for spherical harmonics, µ 1 (A), and Wigner Dfunctions, µ 2 (A), are given by where we adopt the following convention: As a reminder, the problem of designing sensing matrix for spherical harmonics and Wigner D-expansion boils down to finding the sequence of azimuth, elevation, and for Wigner D-functions case, polarization over which the measurements are taken. For spherical harmonics, the sampling pattern is given by pairs (θ p , φ p ) with p ∈ [m], θ p ∈ [0, π] and φ p ∈ [0, 2π). For Wigner D-expansion, a rotation variable should be added and the sampling pattern is given by pairs (θ p , φ p , χ p ) with p ∈ [m], θ p ∈ [0, π] and φ p , χ p ∈ [0, 2π). In the next section, our first result states that many sampling patterns, which are widely used in practice, have high mutual coherence and therefore are inapplicable for compressed sensing.

Modularly Symmetric Patterns over Azimuth and Polarization
A large class of regular sampling patterns select their sampling patterns on a regular grid over θ, φ and χ. Some of these sampling patterns, however, would lead to high mutual coherence and therefore should be avoided for compressed sensing applications. Spherical harmonics and Wigner D-functions are defined by associated Legendre polynomials and Jacobi polynomials. These polynomials are linearly related to each other for different orders and degrees. Through this relation, two columns of the sensing matrix can become strongly coherent in some cases. The following theorem concerns one of these cases. It states the regular sampling on φ and χ can lead to full coherence.
Theorem 4. Let the matrix A ∈ C m×N be constructed from samples of spherical harmonics Y k l (θ, φ) or Wigner D-functions D k,n l (θ, φ, χ). For a signal with bandwidth B, suppose that a given sampling pattern for orders −(B − 1) ≤ k, n ≤ B − 1 satisfies: respectively for spherical harmonics and Wigner D-functions. Then the mutual coherence of this matrix attains its maximum, i.e., µ(A) = 1.
Proof. Associated Legendre polynomials satisfy a symmetry relation over order in the following sense [41]: where C lk = (l−k)! (l+k)! . This relation implies immediately a symmetric relation over orders of spherical harmonics, namely Now if the azimuth sampling points are selected as 2kφ i ≡ 2kφ j mod 2π for all i, j ∈ [m], then the equality e −i2kφ i = e −i2kφ j holds, which implies: for some constant C k . This means that there are two columns of the matrix, corresponding to these two basis functions, totally coherent with each other and therefore yielding the coherence equal to one. On the other hand, it can be easily seen that by inverting the sign of orders of Wigner D-functions, the orders of respective Jacobi polynomial does not change and therefore: which means that If for some k, n, we have 2nχ i + 2kφ i ≡ 2nχ j + 2kφ j mod 2π for all i, j ∈ [m], then similar to spherical harmonics, it holds that: D k,n l (θ, φ, χ) = (−1) n−k D −k,−n l (θ, φ, χ).
And therefore there are two columns that are completely coherent and therefore the mutual coherence is equal to one.
The previous theorem precludes some of familiar sampling patterns. One notable example is equiangular sampling on φ namely, φ p = 2π(p−1) Theorem 4 provides a first step to understand what to avoid in sensing matrix designs. In the next sections, we first provide an alternative way of characterizing coherence using tools originally developed in quantum mechanics. Afterwards, instead of imposing regularity on φ and χ, we study regular sampling on the elevation θ.

Coherence Analysis using Wigner 3j Symbols
Spherical harmonics and Wigner D-functions express wave functions in the study of angular momentum in quantum mechanics. Their products appear in the characterization of total angular momenta of a composite system in terms of the angular momentum of its two sub-systems. This characterization involves a decomposition of the wave function into two wave functions with different angular momenta. The coefficients of this decomposition are given by the Clebsch-Gordan coefficients, also known as Wigner or vector coupling coefficients, as well as Wigner 3j symbols [32,[42][43][44][45]. We focus on the latter and provide briefly some of the useful identities here. Wigner 3j symbols are denoted by l 1 l 2 l 3 k 1 k 2 k 3 ∈ R, and their exact formula is given in [31, Section 7.10.2] or [44]. In quantum mechanics, l i 's and k i 's are non-negative integers or half-odd numbers, however in this paper, we only focus on the case where they are all integers. Despite their complex expressions, Wigner 3j symbols have a few useful properties. The so-called selection rules state that Wigner 3j symbols l 1 l 2 l 3 k 1 k 3 k 3 are non-zero only if: • The absolute value of k i does not exceed l i , i.e., −l i ≤ k i ≤ l i for i = 1, 2, 3 • The summation of all k i should be zero: k 1 + k 2 + k 3 = 0.
• The sum of all l i 's should be an integer.
If one of the above conditions does not hold, the corresponding Wigner 3j symbol will be zero. In coherence analysis of the sensing matrix in (17) and (16), one encounters sums over products of spherical harmonics or Wigner D-functions. We can use Wigner 3j symbols to express these sums in terms of sums of spherical harmonics, or respectively Wigner D-functions. The decomposition reveals in another way the effect of sampling patterns on the mutual coherence. The following proposition, derived from the decomposition based on Wigner 3j symbols, characterizes the inner product between two columns of the sensing matrix.
Proposition 1. Let D k,n l (θ, φ, χ) be the Wigner D-function with degree l and orders k, n, and let Y k l (θ, φ) be the spherical harmonics with degree l and order k. Then the following identities hold: ) wherek = k 2 − k 1 andn = n 2 − n 1 and the phase factor C k 2 ,n 2 = (−1) k 2 +n 2 .
Proof. The product of two Wigner D-functions of degrees l 1 and l 2 and orders k 1 , n 1 and k 2 , n 2 writes in terms of the Wigner 3j symbols as wheren = n 1 + n 2 andk = k 1 + k 2 [44, pp. 61-62]. The spherical harmonics version of the expansion can be obtained by using n 1 = n 2 = 0.
From the conjugate property of these functions, we know that: The proof follows with standard manipulations by plugging in these identities to (25).
According to Proposition 1, the inner product between columns of the sensing matrix depends on the sampling pattern through the sum m p=1 Yk l (θ p , φ p ) or m p=1 Dk ,n l (θ p , φ p , χ p ). The next theorem uses this characterization when the elevation samples are chosen symmetrically in the following sense. Proof. We start with spherical harmonics. We use Proposition 1. Note that: where P l (cos θ) is the Legendre polynomial. Legendre polynomials are odd functions for odd l. This means that for the cosine-symmetric elevation sampling, when l is odd, it holds that: m p=1 P l (cos θ p ) = 0.
Therefore Proposition 1 implies that: On the other hand, according to the selection rules, if l 1 + l 2 is odd andl is even, then l 1 l 2l 0 0 0 = 0, which proves the theorem. A similar argument works for the Wigner D-functions.
Theorem 5 implies that, if the elevation sampling pattern is cosine-symmetric, there are at least B 2 columns that are mutually orthogonal. Cosine-symmetric sampling patterns are also regular, hence, suitable for practical measurements. Using this insight, in the next section, we propose a cosine-symmetric pattern with minimal coherence.

Equispaced Elevation Sampling for Spherical Harmonics and Wigner D-Functions
As we discussed, among regular sampling patterns, equiangular sampling patterns on azimuth and polarization lead to coherent, and therefore undesirable, sensing matrices. On the other hand, a class of regular sampling patterns on the elevation yield incoherent measurements as in Theorem 5.
As soon as the elevation sampling is fixed, the mutual coherence is automatically bounded from below regardless of the choice of azimuth sampling patterns. This is because, in the inner products of columns with equal orders k 1 = k 2 = k and n 1 = n 2 = n, the terms e ik 1 φp and e −ik 2 φp and the terms e in 1 χp and e −in 2 χp cancel each other out. Furthermore the 2 -norm of Y k l (θ, φ) and D k,n l (θ, φ, χ) depends only on elevation sampling for all degrees and orders. We state this simple result in the following proposition. Proposition 2. Let the elevation sampling be fixed to θ 1 , θ 2 , . . . , θ m . For all possible choices of azimuth φ p , and polarization χ p , p ∈ [m], it holds that In particular it holds that where P l (cos θ) is the Legendre polynomial of degree l and P l (cos θ) := (P l (cos θ 1 ), . . . , P l (cos θ m )) T .
The proposition follows by choosing equal orders in the definition of the coherence. Its lower bounds hold in general for any sampling pattern. Note that Theorem 5 implies that: On the face of it, Proposition 2 seems trivial. It indicates the sensitivity of mutual coherence to the choice of elevation sampling alone. The lower bound, however, is almost tight for a class of regular sampling patterns on elevation defined below if m is sufficiently large.
Note that the above sampling points are cosine-symmetric. For the equispaced elevation sampling, for sufficiently large m, the dominant inner product among all the inner products between the spherical harmonics of equal orders is the inner product between degrees of B − 1 and B − 3. This can be clearly seen in Fig. 1. After a certain measurement number m, the inner products between columns of equal orders are completely ordered. The ordering of inner products between two columns, say of degree l 1 and l 2 , corresponds to a partial order defined on the degree pairs (l 1 , l 2 ). This can formally proven. We relegate, however, the detailed derivations of this result to another work [46]. The lower bound is therefore tight in the following sense. Once the elevation sampling pattern is equispaced, there is a fundamental lower bound on the coherence independent of the choice of azimuth and polarization. This lower bound is given in Proposition 2 for sufficiently large m. Note that the number of measurements m should be of O(N 1/2 ) for the tightness of the lower bound in this sense. This dependence on N is in general undesirable and cannot be removed, as it can be seen in the numerical result. The exact inequality, however, involves large constants, so that, for many N 's of practical interest, the number of required measurements for the tightness of the lower bound are small. For example, when N = 1024, Figure 1 show that after 100 measurements, the lower bound becomes tight. In the next section, we provide a way to choose azimuth sampling patterns that achieves the lower bound for spherical harmonics.

Sampling Pattern Design using Coherence Minimization
Is the lower bound of Proposition 2 tight for equispaced sampling patterns? That is, can we find an azimuth sampling pattern that achieves the bound? To do so, we directly minimize the mutual coherence as a figure of merit. The problem of minimizing the mutual coherence for spherical harmonics and Wigner D-functions is non-convex in general since Legendre polynomials, Jacobi polynomials and trigonometric polynomials e i(k (r) −k(q))φp are non-convex. We provide, however, a pattern search algorithm for minimizing the mutual coherence [47]. Pattern search, however, requires less computation time and provides better results in comparison. It is particularly useful as it does not need to calculate the gradient during optimization process. There is, however, no guarantee that the method will converge to the global optimum. See for example [48] for a discussion on the convergence of this algorithm. Although the method has rooms for improvements, it still yields, as we will see, sufficiently good sampling patterns.
First consider spherical harmonics. The algorithm is described in Algorithm 1. It starts by choosing initial φ 0 drawn uniformly at random on the interval [0, 2π) m . The elevation sampling pattern θ is fixed.
The algorithm has two hyperparameters λ and ∆ 0 . The parameter ∆ 0 is the initial update step, and determines the search space, which is spanned along the canonical bases. The update step is decreased iteratively by the decay parameter λ. The algorithm tries to find the minimum coherence and its minimizer by checking the neighbor vectors where the initial update step is given as ∆ 0 . The mutual coherence at the iteration k is denoted by µ(θ, φ k ). If the search fails, the step size is decreased by scaling with λ. The algorithm stops when the number of iteration is achieved a pre-determined maximum or when the difference between the update coherence and the lower bound of Proposition 2, denoted by µ LB , is small |µ(θ, φ k ) − µ LB | ≤ . Figure 2 compares the mutual coherence of the resulting sampling pattern from Algorithm 1 with other sampling patterns widely used in applications. We use spiral [49], Hammersley [50], Fibonacci [51] and equiangular sampling patterns to verify the result of Theorem 4. Another sampling pattern on the sphere is the so-called t-design [52]. Unfortunately, the spherical t-design does not exist for an arbitrary pair m, t as given in [53], which also restricts the flexibility to choose an arbitrary number of samples. To the best of our knowledge there is nothing related to spherical designs on the rotation group.
The bandwidth of spherical harmonics is chosen as B = 10, which yields N = B 2 = 100. We plot also the Welch bound, which is the strict lower bound on the coherence
• Standard basis e i for i ∈ [m].
• Coherence of pair θ, φ ∈ R m is given as µ(θ, φ). Figure 2, interestingly, shows that the obtained sampling pattern achieves the lower bound of Proposition 2 and outperforms with a large margin the other sampling patterns. We have numerically observed that the lower bound can be achieved using our sampling patterns for N up to 10000. Figure 3 shows the distribution of this sampling points on the sphere for different number of samples m, B = 32 and N = B 2 = 1024. 10   Algorithm 1 can be extended to find pairs of (φ p , χ p ), p ∈ [m], for Wigner D-functions. At each step, the algorithm searches simultaneously over the neighbor pairs, and advances similarly by updating ∆ k and φ k , χ k . The mutual coherence of the resulting sampling pattern is shown in Figure 4 and is compared with other sampling patterns. The bandwidth is chosen as B = 4, hence, N = B(2B−1)(2B+1) of Proposition 2 does not improve on the Welch bound for Wigner D-functions. Although the resulting sampling pattern outperforms significantly the other sampling patterns, it does not achieve the lower bound. This might be an artifact of our optimization method. 10   A concern about our pattern search algorithm is computational complexity. For N = 49 and N = 100 and the error tolerance of |µ(θ, φ k ) − µ LB | ≤ = 10 −4 , the computation time of the algorithm is shown in Figure 5. When we double the dimension of the signal, it is apparent that the computation time to achieve the same error tolerance would increase approximately fivefold.

Experimental Results
In the previous section, we designed two equispaced sampling patterns, one for the sphere and one for the rotation group with better mutual coherence. In this section, we see if this superiority is translated to the sparse recovery performance as well. Besides, the performance of our proposed sampling patterns is compared with random sampling patterns, which are provably good with high probability for sparse recovery. Two random sampling patterns are considered. The first one is proposed in [9] with the uniform measure, i.e., dν = dθdφ for S 2 and dν = dθdφdχ for SO (3). The second one is given in [10] with the measure dν = | tan θ| 1/3 dθdφ for S 2 and dν = | tan θ| 1/3 dθdφdχ for SO(3).

Phase transition diagrams
Consider the span of band-limited spherical harmonics with B = 10, that is N = B 2 = 100. We use the equispaced sampling pattern with θ p as cos θ p = 2p−m−1 m−1 , p ∈ [m], and the 21 azimuth samples φ p chosen from Algorithm 1. We solve the linear inverse problem without additive noise using the l 1 -norm minimization package YALL1 [54]. The phase transition diagram of our proposed sampling pattern is plotted with 50 trials and error threshold 10 −3 . Figure 6 compares the recovery performance of the proposed sampling pattern with several well-known sampling patterns on the sphere and, as well, random sampling. Not only our proposed sampling gives better recovery performance compared with many regular sampling patterns, it even gives a slightly better sparse recovery performance compared with the two random sampling patterns.   Figure 7 shows the phase transition for the l 1 -minimization. Although our proposed sampling pattern for Wigner D-functions does not achieve the lower bound, it still outperforms other regular sampling patterns, and even slightly random sampling patterns. The comparison between several recovery algo-   Figure 8 for Wigner D-functions, where besides BP, the Orthogonal Matching Pursuit (OMP) [55] and the Approximate Message Passing (AMP) [56] are also implemented. It can be seen that the proposed sampling pattern performs slightly better than the random sampling. Furthermore, OMP algorithm delivers better recovery in this case. In this case, the sparsity s = 20 is considered and the non-zero values are drawn from random zero mean and unit variance Gaussian distribution. Signal recoveries are conducted with 30 trials.

Spherical near-field antenna measurements
One of the main applications of sparse recovery on S 2 and SO (3) is spherical near-field antenna measurement [57]. The expression of electromagnetic field of the antenna using Wigner D-basis coefficients is described as follows where y(θ, φ, χ) is a band-limited near-field signal with Wigner D-functions as basis, h denotes the both transverse electric (TE) and magnetic (TM), n and χ denote order and angle to measure polarization, respectively. The bandwidth B is obtained by calculating the wavenumber k and minimum sphere that could cover the whole antenna with radius r 0 . The bandwidth is given by B = kr 0 + 10, where the factor 10 is usually added as a correction factor. Normally, it is desirable to measure co-and cross-polarization of the antenna and to use n = ±1, with angle χ ∈ {0, π/2}. The goal is to estimate the spherical wave coefficients of the antenna under test, i.e., T hlk in near-field measurements and use it to determine far-field patterns. The classical method [57] uses Fourier analysis with equiangular samples to get the spherical wave coefficient T hlk and lacks the freedom to choose different sampling patterns. In the real measurement systems, the measurement time directly scales with the number of required samples.
In the classical method, we have to take m ≥ 2(B + 1)(2B + 1). The spherical wave coefficients, however, are sparse with respect to Wigner D-basis, which calls for compressed sensing methods. It can be seen in Figure 9 that the important spherical wave coefficients, which is represented by the high intensity of the amplitude, are compressible. In order to get better understanding of spherical near-field measurements we refer to [57,58]. Figure 9 shows the estimation of spherical wave coefficients by using basis pursuit for antenna horn SAS-571. The bandwidth in this case is given by B = 30, which means N = 960. Note that the number of coefficients are twice this number, namely 1920, because of the TE/TM coefficient h. It can be seen that the proposed sampling manages to recover same spherical wave coefficients as the conventional method with smaller number of measurements, namely m = 900. As it has been shown in [59], our proposed sampling The equiangular sampling pattern fails to estimate the spherical wave coefficients. This can be seen as well in far-field signal reconstructions. Figure 10 and Figure 11 show this for polarization χ = 0 • and χ = 90 • , respectively. It is assumed that the classical method gives a very good approximation of the ground truth. In comparison, our sampling patterns matches closely the output of the classical method while the equiangular sampling pattern fails to reconstruct the far-field.

Earth magnetic fields
It is also possible to apply our proposed sampling points to the International Geomagnetic Reference Field (IGRF) model. IGRF model uses the gradient of magnetic scalar potential to describe the earth's geomagnetic field and it can be expressed by using spherical harmonics expansion as a B−1 l=1 l k=0 a r l+1 g k l (t) cos kφ + h k l (t) sin kφ P k l (cos θ), where a is the Earth's radius, r is radial distance from the Earth's center. The time varying Gauss coefficients are given as g k l (t), h k l (t). In this case, P k l (cos θ) is the normalized associated Legendre polynomials with degree l and order k, where the normalization factor is (−1) k 2(l−k)! (l+k)! . In this numerical result, we will consider the 2015 measurements model [12] with band-limited spherical harmonics B = 14, thus the size of spherical harmonics coefficients is given by N = 196. The magnetic field is sampled using equiangular, Hammersley and proposed sampling points with number of samples m = 53. From these samples, sparse coefficients of spherical harmonics are estimated by using BP and projected into spherical harmonics with fine grid resolution on θ ∈ [− π 2 , π 2 ] and φ ∈ [0, 2π). Figure 12 shows the comparison of the original and the reconstruction magnetic fields after projecting the spherical harmonics coefficients to spherical harmonics matrix with fine resolution. It can be seen the proposed sampling points perform slightly better re-  Figure 12: Reconstruction of the earth magnetic field by using CS with different sampling patterns construction than Hammersley sampling points to reconstruct the earth's magnetic field by using BP. As mentioned earlier, the equiangular sampling points deliver the worst reconstruction among the sampling points.

Conclusion and Future Works
How can we find a sampling pattern on the sphere and the rotation group that is also suitable for compressed sensing of signals? By proving RIP property, we show that, as it is expected, random sampling patterns can provably be used for signal recovery on the rotation group. The obtained bound depends on the ambient dimension. Future works can focus on improving this dependency by using a change-of-measure similar to [10]. It is currently not clear how the framework of [10] can be adapted for Wigner D-functions.
It is interesting to see if the bounds can be improved to only include logarithmic and poly-logarithmic dependencies on N . Given the interest in regular sampling patterns in many applications, we consider various existing regular patterns as well. Interestingly, many patterns with symmetric structure on azimuth and polarization suffer from high mutual coherence and are essentially unsuitable for compressed sensing. Instead, we propose a new sampling pattern that imposes regularity on elevation. Using tools from angular momentum analysis in quantum mechanics, we show how appropriate elevation sampling patterns can yield mutually incoherent measurements. We show that it is possible to match the lower bound on the coherence for the sphere using a simple coherence minimization algorithm. The phase transition diagrams show that our proposed sampling patterns outperform other regular patterns and surpass even random sampling patterns.
Future works can focus on closing the gap, for the rotation group, between the lower bound and the proposed sampling pattern. This can be done either by deriving new lower bounds or by more effective optimization approaches. Another line of research can focus on RIP-free recovery guarantees applicable to deterministic patterns. We have numerically shown, by using several well-known recovery algorithms, that the proposed sampling points perform better recovery than random as well as the popular regular sampling points. However, the uniform recovery guarantees for the deterministic sampling points suffer from the quadratic bottleneck. Certain works already exist that use numbertheoretic construction of [33] for a deterministic sensing matrix. The extension of these methods to S 2 and SO (3) is an interesting and non-trivial problem.