\documentclass[twoside]{article} \usepackage{amsmath, amssymb} \pagestyle{myheadings} \setcounter{page}{15} \markboth{\hfil Compression on the digital unit sphere \hfil} {\hfil Mohamed Allali \hfil} \begin{document} \title{\vspace{-1in}\parbox{\linewidth}{\footnotesize\noindent {\sc 16th Conference on Applied Mathematics, Univ. of Central Oklahoma}, \newline Electronic Journal of Differential Equations, Conf. 07, 2001, pp. 15--24. \newline ISSN: 1072-6691. URL: http://ejde.math.swt.edu or http://ejde.math.unt.edu \newline ftp ejde.math.swt.edu (login: ftp)} \vspace{\bigskipamount} \\ % Compression on the digital unit sphere % \thanks{ {\em Mathematics Subject Classifications:} 42C40, 41A17. \hfil\break\indent {\em Key words:} Wavelets on the sphere, equidistribution, spherical caps. \hfil\break\indent \copyright 2001 Southwest Texas State University. \hfil\break\indent Published July 20, 2001.} } \date{} \author{ Mohamed Allali } \maketitle \begin{abstract} A method for compressing functions on the unit sphere is presented. This method is based on a Ramanujan set of rotations, and generates an equidistributed system of points. This method is flexible and easy to implement as it needs only few transformations to cover the whole unit sphere with spherical caps. \end{abstract} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}{Lemma}[section] \newtheorem{proposition}{Proposition}[section] \renewcommand{\theequation}{\thesection.\arabic{equation}} \catcode@=11 \@addtoreset{equation}{section} \catcode@=12 \section{Introduction} One of the most common applications of wavelet theory is data compression. We propose a new method to compress square integrable functions on the unit sphere. The main tools used in this analysis are a Ramanujan set of rotations and planar wavelets. Ramanujan sets of rotations are introduced in Section 2 and our focus is on $S_5^M$, a special set from the Ramanujan set of rotations. Starting with a point on the digital sphere and using $S_5^M$ we can generate points on the sphere. The equidistribution of these generated points and the uniformity of this distribution in terms of quadrature on the sphere is studied in Section 3. In the algorithm proposed in Section 5, the method of covering the sphere by means of spherical caps of fixed radius is needed. Therefore we derive in Section 4 a precise formula to cover the unit sphere with a given radius. \section{A Ramanujan set of rotations } In order to study covering and equidistribution on the unit sphere, we shall introduce a special set called the Ramanujan set of rotations \cite{LPS}. Let $S^2=\{x\in {\mathbb R}^3;\ |x|=1\}$ be the unit sphere and let $d\sigma$ denote the usual rotation invariant measure on $S^2$ defined by $$\int_{\mathbb {R}^3} f(x)\,dx = \int_0^\infty \int_{S^2} f(r\sigma) \,d\sigma\,r^2\,dr,$$ where $f$ is a continuous compactly supported function on ${\mathbb R}^3$. We are interested in the Hilbert space $L^2(S^2)$ of square integrable functions on the sphere, with the usual scalar product: $$(f,g)=\int_{S^2}f(\sigma)\overline{g(\sigma)}\,d\sigma \qquad (f,g\in L^2(S^2)).$$ The corresponding norm of a function $f\in L^2(S^2)$ is $\| f\|=\sqrt{(f,f)}$. The group $G=SO(3)$ of proper rotations preserving the dot product acts on this space as follows: $$\rho(\gamma)f(\sigma)=f(\gamma^{-1}\sigma), \label {1}$$ where $\gamma\in G,\ \sigma\in S^2$, and$\ f\in L^2(S^2))$. Each operator $\rho(\gamma)$ defined in (1) is unitary. For any $f,g\in L^2(S^2)$ the function $G\ni \gamma\to (\rho(\gamma)f,g)\in {\mathbb C}$ is continuous. Moreover, $\rho(\gamma_1)\rho(\gamma_2)=\rho(\gamma_1\gamma_2)$ for any $\gamma_1,\gamma_2\in G$. In other words, $(\rho, L^2(S^2))$ is a unitary representation of the group $G$ \cite{K}. Let $S\subseteq SO(3)$ be a finite symmetric set. In other words, the number of elements of $S$, denoted by $\left| S \right|=2N,$ is even and $\gamma \in S$ if and only if $\gamma^{-1} \in S$. Let $(T_{S}f)(x)=\sum_{\gamma\in S}f(\gamma x)$, where $f\in L^2(S^2)$. Furthermore, let $u(x)=1$, $x \in S^2$, denote the unit function and $\mathcal{H}_0={\mathbb C} u$. We would like to approximate the projection $P_{\mathcal{H}_0}$ by ${1\over |S|}T_S$ for suitable $S$. The first problem is to agree on a way to measure the error for such an approximation. For an operator $T:L^2(S^2)\to L^2(S^2)$ let $\| T\|$ be the operator norm of $T$. Explicitly, $\| T\|$ is the supremum of the numbers $\| T(f)\|$, where $f\in L^2(S^2)$ and $\| f\| =(\int {\left| {f(x)} \right|}^2dx)^{1/2}= 1$. The orthogonal projection $P_{\mathcal{H}_0}: L^2(S^2)\to \mathcal{H}_0$ is given by: $$P_{\mathcal{H}_0}f=({1\over{4\pi}} \int_{S^2}f(x)\,dx\,) u$$ where $f\in L^2(S^2).$ We agree that our approximation is best when the norm $$\| {1\over{|S|}}T_S - P_{\mathcal{H}_0}\|$$is minimal. \bigskip \begin{theorem} For any finite symmetric set $S\subseteq SO(3)$ $$\| {1\over{|S|}}T_S - P_{\mathcal{H}_0}\| \geq 2{{\sqrt{|S|-1}}\over{|S|}}.$$ \end{theorem} A set where the equality holds is called a {\bf Ramanujan set}. Let $p$ be a prime, equal to $1$ modulo $4$. Then there exists in \cite{LPS} an explicitly described Ramanujan set, $S_p$, with $|S_p|=p+1$. \section{Equidistribution on the unit sphere} Of practical importance is the problem of generating equidistributed points on the sphere. The problem of generating a large number of points on the sphere has many applications in various fields of computation such as quadrature, placing grids on $S^2$, tomography, coding theory, etc. See \cite{C,S,T}, for example. The advantage of an equidistributed system of points lies in the fact that relatively few samplings of the data are needed, and approximate integration can be performed by computation of a mean value, i.e. the arithmetical mean. Let $S_p=\{ \gamma _1,\dots,\gamma _{{{p+1}\over 2}},\gamma _1^{-1}, \dots,\gamma _{{{p+1} \over 2}}^{-1}\}$ be a Ramanujan set as defined earlier, and let $S_p^M\subseteq SO(3)$ denote the set of reduced words of length at most $M=1,2,3,\dots$ in $S_p$ (by reduced we mean all the obvious cancellations such as $\gamma \gamma^{-1}$ have been carried out). It is easy to verify that $$\left| {S_p^M} \right|={{p^{M+1}+p^M-p-1} \over {p-1}}. \label {2}$$ The following theorem gives the quadrature error bound for the Ramanujan set and it is near-optimal for the numerical integration of functions on $S^2$. \begin{theorem} $$\left\| {{1 \over {\left| {S_p^M} \right|}}T_{S_p^M}-P_{\mathcal{H}_0}} \right\|\le \mathrm{const}{{\log (\left| {S_p^M} \right|)} \over {\sqrt {\left| {S_p^M} \right|}}}.$$ \end{theorem} \bigskip \noindent {\bf Example 3.1.} For $p=5$, the construction can be described concisely. $S_5=\{ A,B,C,A^{-1},B^{-1},C^{-1}\}$, where $A$, $B$, and $C$ are rotations about the $X$, $Y$, and $Z$ axes, each through an angle of $\arccos (-{3 \over 5})$. Therefore, $S_5^M = \{A,B,C,A^{-1},\\ B^{-1},C^{-1},AA,AB,AB^{-1},\dots\}.$ A substitution in (2) using $p=5$, the set $S_5^M$ contains ${3 \over 2}(5^M-1)$ elements of rotations. This construction is just the simplest one from an infinite family; for each prime $p$ congruent to 1 modulo 4, there is a construction involving $p+1$ generator rotations, which corresponds to ways of writing $p$ as the sum of four squares of integers with the first addend being positive and odd \cite{LPS}. \medskip We will use the set $S_5^M$ discussed in Example 1 to generate points on the unit sphere. A stereographic projection can be used to relate points in the complex plane ${\mathbb C}$ to points on the sphere. To every point $\xi=(\xi_1,\xi_2,\xi_3)^T$ on the unit sphere, except the north pole $(0,0,1)^T$, we associate a complex number $$z={{\xi _1+i\xi _2} \over {1-\xi _3}}.$$ Under this stereographic projection the fractional linear transformations in the complex plane correspond to rotations on the sphere. Taking this into account, it is convenient to actually compute with points in ${\mathbb C}$ and to use fractional transformations instead of rotations. The rotation group $SO(3)$ is mapped onto $SU(2)$, with homographic action on ${\mathbb C}$ : $$z\longrightarrow {az+b \over cz+d},\ \ \left( \begin{matrix}{ a}&{b}\cr {c}&{d}\end{matrix}\right) \in SU(2).$$ So $z$ transforms to ${\tilde z}$ as $${\tilde z}={az+b \over cz+d}.$$ The $A,$ $B,$ and $C$ correspond to the linear fractional transformations defined by the matrices $$A_p={1 \over {\sqrt 5}}\left( \begin{matrix}{1+2i}&0\cr 0&{1-2i}\cr \end{matrix}\right),\quad B_p={1 \over {\sqrt 5}}\left( \begin{matrix} 1&2\cr -2 &1\end{matrix} \right)$$ and $$C_p={1 \over {\sqrt 5}}\left(\begin{matrix} 1&{2i}\cr {2i}&1\end{matrix}\right).$$ The final step in the process is to project ${\tilde z}$ back to the unit sphere via the inverse stereographic projection. A rotated point ${\tilde \xi} = ({\tilde \xi_1},{\tilde \xi_2},{\tilde \xi_3})^T$ on the unit sphere is related to ${\tilde z}$ by $$({\tilde \xi_1},{\tilde \xi_2},{\tilde \xi_3})^T=({2\Re ({\tilde z})\over 1+{| {\tilde z} |}^2},{2\Im ({\tilde z})\over 1+{| {\tilde z} |}^2}, {{| {\tilde z}|}^2-1 \over 1+{| {\tilde z}|}^2}).$$ \section{Covering of the sphere} This led to the investigation of the general question: how many spherical caps of radius $h$ do we need to cover the unit sphere? We are looking for an explicit formula for the number of spherical caps needed and an exact positioning of the centers of the spherical caps that cover the whole unit sphere without giving any preferences to any region on the sphere. We will use in this work the Ramanujan set of rotations only in the case when $p=5$. Let $A\subseteq S^2$ be a spherical cap with center $y \in S^2$ and radius $h$. The area $\left| A \right|=2\pi h$. Denote by $\chi_A$ the characteristic function of $A$. In order for the set$\{ \gamma A\} _{\gamma \in S_5^M}$ to cover the whole unit sphere, one has to make sure that for every $x \in S^2$, there exists at least one spherical cap, say $\gamma A$, where $\gamma \in S_5^M$, such that $x \in \gamma A$. \begin{theorem} Let $C_M=5^{{M \over 2}}(M+1+{M \over {\sqrt 5}})$, and let $k=4{{(16+\sqrt \pi )} \over \pi }$. Then, for every cap $A\subseteq S^2$ and for all $x \in S^2$ we have $$\Big| {\left| A \right|-{1 \over {\left| {S_5^M} \right|}} \sum\limits_{\gamma \in S_5^M} {\chi _{\gamma A}(x)}} \Big| \le {3 \over {4^{1/3}}}(4\pi )^{1/3} \Big[ {C_M \over {\left| {S_5^M} \right|}}k \Big]^{2/3}.$$ \end{theorem} Furthermore, in order to use \cite[Theorem 4.1]{A} to guarantee the covering of the sphere, we need the following lemma. \vskip6pt \begin{lemma} % Lemma 4.1. $$\Big| {\left| A \right|-{1 \over {\left| {S_5^M} \right|}} \sum\limits_{\gamma \in S_5^M} {\chi _{\gamma A}(x)}} \Big|< |A| \Rightarrow \bigcup_{\gamma \in S_5^M} \gamma A =S^2.$$ \end{lemma} \noindent {\bf Proof.} As $\gamma A \subseteq S^2$, then $\bigcup_{\gamma \in S_5^M} \gamma A \subseteq S^2.$ Now, letting $x \in S^2$ we have $$\Big| {\left| A \right|-{1 \over {\left| {S_5^M} \right|}} \sum\limits_{\gamma \in S_5^M} {\chi _{\gamma A}(x)}} \Big|<|A| \Rightarrow \sum\limits_{\gamma \in S_5^M} {\chi _{\gamma A}(x)}\ne 0.$$ So, we can see that there exists a $\gamma \in S_5^M$ such that ${\chi _{\gamma A}(x)} =1$. This is equivalent to saying that $x \in \gamma A$. As $\gamma A \subseteq \bigcup_{\gamma \in S_5^M},$ the lemma follows. Based on this fact and on Theorem 4.1, we reach a covering if $${3 \over {4^{1/3}}}(4\pi )^{1/3} \Big[ {C_M \over {\left| {S_5^M} \right|}}k \Big]^{2/3}<{2\pi h}. \label {3}$$ As $n={3 \over 2}(5^M-1)$, then $M=\log _5({{2n} \over 3}+1)$, and $5^{{M \over 2}}=\sqrt {{2 \over 3}n+1}$. Inequality (3) can be simplified as follows $${{\sqrt {{2 \over 3}n+1}\left[ {1+(1+{1 \over {\sqrt 5}}) \log _5({{2n} \over 3}+1)} \right]} \over n}<{{{1 \over 6}\sqrt {{2 \over 3}} \pi ^2} \over {16+\sqrt \pi }}h^{3/2}.$$ The left hand side of the previous inequality is less than $${\sqrt 2\sqrt {(2/3)}\sqrt n\, 2(1+{1 \over {\sqrt 5}})\log _5n \over n}$$ and so we have proven the following proposition. \begin{proposition} % Proposition 4.1. If $n$ satisfies the inequality $${{\log n} \over {\sqrt n}} < {{\sqrt 5(\log 5)\pi ^2} \over {12\sqrt 2(\sqrt 5+1)(16+\sqrt \pi )}}h^{3/2},$$ then the sphere covering is guaranteed, $$\bigcup_{\gamma \in S_5^M} \gamma A =S^2\,.$$ \end{proposition} \section {Compression on the unit sphere} We propose a method for compressing functions on the sphere based solely on a Ramanujan set of rotations and planar wavelets. This method was inspired by the fact that a rigorous method needs to perform uniformly well independently of the location of the support of the function on the sphere, and for functions supported in a small (relatively flat) subset of $S^2$, this method should be similar to the one obtained from the theory of wavelets on ${\mathbb R}^2$. The 2-sphere $S^2$ can not be embedded homeomorphically into the Euclidean plane $\mathbb{R}^2$. For, if a topological mapping of $S^2$ onto a subset $M$ of $\mathbb{R}^2$ existed, then $M$ would be, like $S^2$, compact and simply connected and consequently isomorphic to the closed disk. The Euler number of the disk $(\chi=1),$ however, differs from that of the sphere $(\chi=2)$. Thus there is no atlas of $S^2$ which consists of only one chart. To put it another way, every chart of the sphere has a singularity. This fact, known to cartographers for many centuries, complicates the positioning of points on the sphere considerably. Let $$SP:S^2\setminus\{\text{North Pole}\}\to {\mathbb R}^2$$ be the stereographic projection, (see \cite{Mu}). Let $\Psi$ be an orthonormal basis of $L^2({\mathbb R}^2)$ constructed using tensor products of some orthogonal wavelet basis of $L^2({\mathbb R})$. Let $SP^*(\Psi)\subseteq L^2(S^2)$ be the orthonormal basis of $L^2(S^2)$ obtained by pulling back the functions from $\Psi$ to the sphere, and normalizing them appropriately, using the Jacobian of the stereographic projection. Then $SP^*(\Psi)$ is an orthonormal basis of $L^2(S^2)$. However, the members of this basis supported near the South Pole look very different than the members supported near the North Pole as the North Pole is a singular point. In order to avoid this singularity we shall rotate the North Pole, using a well distributed set of rotations, namely the Ramanujan set of rotations $S_5^M$. What follows is a description of our new method for compressing functions on the unit sphere. Let $F(\xi_1,\xi_2,\xi_3)$ be a function belonging to $L^2(S^2)$. We project it onto the complex plane via the stereographic projection $SP$. Let us find first the Jacobian $J$ of this transformation, taking into consideration the fact that $\xi_1^2+\xi_2^2+\xi_3^2=1$ $$J=\left|\begin{matrix} {\partial x \over \partial \xi_1} &{\partial x \over \partial \xi_2}\cr {\partial y \over \partial \xi_1}&{\partial y \over \partial \xi_2} \end{matrix} \right|^{-1}.$$ Furthermore, we have $${\partial \xi_3 \over \partial \xi_1}={-\xi_1 \over \xi_3}\ \ \text{and} \ \ {\partial \xi_3 \over \partial \xi_2}={-\xi_2 \over \xi_3}.$$ Using this fact we have the following expression for $J$ $$J=\left| \begin{matrix}{1-\xi_3-{\xi_1^2\over \xi_3} \over (1-\xi_3)^2} &{{-\xi_1\xi_2 \over \xi_3} \over (1-\xi_3)^2}\cr {{-\xi_1\xi_2 \over \xi_3} \over (1-\xi_3)^2} & {1-\xi_3-{\xi_2^2\over \xi_3} \over (1-\xi_3)^2}\end{matrix}\right|^{-1}.$$ After simplification we get $$J={-1\over \xi_3(1-\xi_3)^2}.$$ The previous expression can be written in terms of $z={\xi_1+i\xi_2\over 1-\xi_3}$. If we write $\xi_3$ in terms of $z$ as $$\xi_3={{| z|}^2-1 \over 1+{| z|}^2}$$ then an expression of $| J |$ in terms of $z$ is $$| J(z) |={4| 1-| z|^2 | \over 1+{| z|}^2}.$$ The new function on the complex plane is $$f(x,y)=F({2x\over 1+{| z |}^2},{2y\over 1+{| z |}^2}, {{| z|}^2-1 \over 1+{| z|}^2})\cdot{| J(z)|}^{1/2}$$ where $z=x+iy$ and $| z| =\sqrt{x^2+y^2}$. Using the two dimensional wavelets on the plane we can therefore expand $f$ in terms of the wavelet basis in $L^2({\mathbb R}^2)$. For any function $f \in L^2({\mathbb R}^2)$ we have $$f(x,y)= \sum_{i=1}^3 \sum_{j,k,l}(f,{\tilde \psi_i}(2^jx-k,2^jy-l)){\tilde \psi_i}(2^jx-k,2^jy-l)$$ where $\tilde \psi_1=\psi_1 \otimes\psi_2,$ ${\tilde \psi_2}=\psi_1\otimes\phi_2$ and ${\tilde \psi_3}=\phi_1 \otimes\psi_2$ with $j,k,l \in \mathbb{Z}$ and $\psi_1,$ $\psi_2,$ $\phi_1$ and $\phi_2$ are respectively the one dimensional wavelets and scaling functions. Decomposing the function we get $$f(x,y)=A_{\gamma_0}(x,y)+D_{\gamma_0}(x,y)$$ where $A_{\gamma_0}$, and $D_{\gamma_0}$ are respectively the approximation function and the detail function on the plane. As no rotation is performed, we have used $\gamma_0=id$. The next step in the algorithm is to rotate the function $F$ on the unit sphere and then project it to the complex plane, but as the rotation group $SO(3)$ is mapped onto $SU(2)$, with homographic action on ${\mathbb C}$: $$z\mapsto {az+b \over cz+d},\ \ \left( \begin{matrix}{a}&b\cr c&{d}\end{matrix}\right) \in SU(2)$$ we will project $F$ first onto the plane and then use the above transformation which is much easier to implement than the regular $3\times 3$ rotations on the sphere. The scheme goes as follow: $$F(\xi_1,\xi_2,\xi_3)\longrightarrow f(z)\longrightarrow f({az+b \over cz+d})\cdot{1\over {| cz+d|}^2}$$ where $z={\xi_1+i\xi_2 \over 1-\xi_3}$. Furthermore, the matrix $\left( \begin{matrix}{a}&b\cr c&{d}\end{matrix}\right)$ belongs to $SU(2)$ and it corresponds to reduced words formed by $A_p$, $B_p$, and $C_p$ discussed in Section 3. We decompose this new rotated function into the wavelet basis functions to get this time the approximation and detail functions $A_{\gamma_j}$ and $D_{\gamma_j}$ where $\gamma_j$ belongs to the Ramanujan set $S_5^M$. We choose the set $S_5^M$ and not any other arbitrary set of rotations for the main reason that this set generates a uniform distribution on the sphere. Moreover we derived a precise formula in Proposition 1 that provides us with the number of spherical caps of radius $h$ needed to cover the whole unit sphere. We have then $$f(\Re ({\tilde z}),\Im ({\tilde z}))=A_{\gamma_j} (\Re ({\tilde z}),\Im ({\tilde z}))+D_{\gamma_j}(\Re ({\tilde z}),\Im ({\tilde z}))$$ where $${\tilde z}={a_j z+b_j \over c_j z+d_j},$$ and $$\left( \begin{matrix}{a_j}&b_j\cr c_j&{d_j}\end{matrix}\right) \in SU(2).$$ Suppose that we stop this process at level $M$, then we need to pick the rotation that will assure the best approximation, say $\gamma_{j_0}$. We may choose $\gamma_{j_0}$ so that $$\Vert A_{\gamma_{j_0}}(\Re ({\tilde z}),\Im ({\tilde z}))\Vert=\max_{\gamma_j\in S_5^M}\Vert A_{\gamma_j}(\Re ({\tilde z}),\Im ({\tilde z}))\Vert.$$ Using the following decomposition $$f(\Re ({\tilde z}),\Im ({\tilde z}))=A_{\gamma_{j_0}}(\Re ({\tilde z}), \Im ({\tilde z}))+D_{\gamma_{j_0}}(\Re ({\tilde z}),\Im ({\tilde z})),$$ the details and approximations at the first level of resolution are at hand, we can compress now the function on the plane based on standard compression procedures on the plane to get ${\tilde f}((\Re ({\tilde z}),\Im ({\tilde z}))$ as the compressed function. The original $F(\xi_1,\xi_2,\xi_3)$ is defined on the unit sphere, hence the compressed function needs to be projected and rotated back on the sphere. This time, the rotation will precede the projection because we are still processing signals on the complex plane. If $${\tilde z}={az+b \over cz+d}$$ then $$z={-d{\tilde z}+b \over c{\tilde z}-a}.$$ The rotation ${\gamma_{j_0}}^{-1}$ is associated with $\left(\begin{matrix}{\tilde a}_{j_0}&{\tilde b}_{j_0}\cr {\tilde c}_{j_0}&{\tilde d}_{j_0}\end{matrix}\right)$ which satisfy $$\left( \begin{matrix}{\tilde a}_{j_0}&{\tilde b}_{j_0}\cr {\tilde c}_{j_0}&{\tilde d}_{j_0}\end{matrix}\right) = \left(\begin{matrix}{-d}_{j_0}&{b}_{j_0}\cr {c}_{j_0}&{-a}_{j_0}\end{matrix}\right)$$ where $\left( \begin{matrix}{ a}_{j_0}&{ b}_{j_0}\cr {c}_{j_0}&{ d}_{j_0}\end{matrix}\right)$ is the matrix associated with $\gamma_{j_0}$. Note that both matrices $\left(\begin{matrix}{ a}_{j_0}&{ b}_{j_0}\cr {c}_{j_0}&{ d}_{j_0}\end{matrix}\right)$ and $\left(\begin{matrix}{\tilde a}_{j_0}&{\tilde b}_{j_0}\cr {\tilde c}_{j_0}&{\tilde d}_{j_0}\end{matrix}\right)$ belong to $SU(2)$. The function ${\tilde f}$ is now a function of $\Re(z)$ and $\Im(z)$ where $\displaystyle z={-d{\tilde z}+b \over c{\tilde z}-a}$. The final step in the algorithm is to use the inverse stereographic projection to pull back the function ${\tilde f}$ to the unit sphere. The Jacobian of the inverse stereographic projection is $${1\over J}=-\xi_3(1-\xi_3)^2.$$ Finally, the compressed function ${\tilde F}$ on the unit sphere is $${\tilde F}(\xi_1,\xi_2,\xi_3)={\tilde f}({2\Re (z)\over 1+{\| z \|}^2},{2\Im (z)\over 1+{\| z \|}^2}, {{| z|}^2-1 \over 1+{| z|}^2})\cdot {1\over {| J(z)|}^{1/2}}.$$ For the algorithm to perform uniformly well independently of the location of the support of the function on the sphere we shall show that functions supported on a small region $\Omega$ of $S^2$ benefit from the proposed algorithm. This will follow from the next theorem. \begin{theorem} The algorithm described above is based on a finite set of numbers ( finite impulse response filters). Suppose a function $f \in L^2(S^2)$ is supported in a spherical cap $\Omega_h$, of radius $h$ centered at $\xi \in S^2$. let $\Omega$ denote the spherical cap of radius $2h$ centered at the south pole $(0,0,-1)^T$. Let $M>0$ be the smallest integer satisfying the inequality $${{\log n} \over {\sqrt n}} < {{\sqrt 5(\log 5)\pi ^2} \over {12\sqrt 2(\sqrt 5+1)(16+\sqrt \pi )}}h^{3/2},\ \ {\text where} \ \ n={3 \over 2}(5^M-1).$$ Then there is a rotation $\gamma_0\in S_5^M$ such that $\gamma_0 \Omega_h \subseteq \Omega$. In particular, our algorithm will approximate the function $f$ as well as if $f$ was supported in $\Omega$. As a consequence, the performance of the algorithm does not depend on the location of the support of the function $f$. \end{theorem} \noindent {\bf Proof.} The main components of our algorithm are the three matrices $A_p$, $B_p$, and $C_p$ described in Section 3, and the wavelet finite impulse response filters on the plane. Therefore, the algorithm is based on a finite set of numbers. We have shown in Proposition 1 that if $M$ is the level of rotations of $S_5^M$, then it suffices that $n$ satisfies the following inequality for the covering of the unit sphere to be achieved $${{\log n} \over {\sqrt n}} < {{\sqrt 5(\log 5)\pi ^2} \over {12\sqrt 2(\sqrt 5+1)(16+\sqrt \pi )}}h^{3/2},\ \ {\text where}\ \ n={3 \over 2}(5^M-1).$$ So $$\bigcup_{\gamma \in S_5^M} \gamma \Omega_h =S^2.$$ Hence $$\Omega \subseteq \bigcup_{\gamma \in S_5^M} \gamma \Omega_h.$$ Since the radius of $\Omega$ is twice larger as the radius of $\Omega_h$ we see that there is a $\gamma_0 \in S_5^M$ such that $$\gamma_0 \Omega_h\subseteq \Omega.$$ Therefore, the performance of the algorithm is checked for any arbitrary region on the unit sphere. \begin{thebibliography}{00} \frenchspacing \bibitem{A} Allali M., Digital signal processing on the unit sphere via a Ramanujan set of rotations and planar wavelets", Ph.D. thesis, University of Oklahoma, Mathematics and Computer Engineering Department, July 2000. \bibitem{C} Cui J., Finite pointset methods on the sphere and their application in physical geodesy", Ph.D. thesis, University of Kaiserslautern, Geomathematics Group, Germany, 1995. \bibitem{K} Kirillov A., {\it Elements of the theory of representations}, New York: Springer-Verlag, 1976. \bibitem{LPS} Lubotzky A., Phillips R., and Sarnak P., Hecke operators and distributing points on the sphere I", {\it Comm. Pure Appl. Math.}, vol. 39, pp. 149-186, 1986. \bibitem{Mu} M\"uller C., {\it Analysis of Spherical Symmetries in Euclidean Spaces}, Springer-Verlag, 1998. \bibitem{S} Sloane N. J. A., Encrypting by random rotations", {\it Cryptograph, Lecture Notes in computer Science,} vol. 149, Berlin: Springer-Verlag, pp. 522-529, 1983. \bibitem{T} Tichy R., Random points in the cube and on the sphere with applications to numerical analysis", {\it Comput. Appl. Math.} vol. 31, pp. 191-197, 1990. \end{thebibliography} \bigskip \noindent\textsc{Mohamed Allali} \\ Department of Computer Science, Mathematics and Physics \\ Chapman University \\ Orange, CA 92802, USA \\ e-mail: allali@chapman.edu \end{document}