TITLE: An alternate analysis to the (worst-case) run time of the euclidean algorithm
QUESTION [2 upvotes]: I was trying to figure out the running time of the euclidean algorithm. The analysis that I found on Wikipedia and CLRS both analyze the run time of the euclidean algorithm using the Fibonacci recurrence (which I feel is rather unintuitive, so I was looking for something different). However, I remember reading a different analysis and that one can argue that it does at most $2n$ operations where $n = O(\log{b})$ (i.e. the number of bits). I remember that the argument went something like this: "In the worst case, Euclid's algorithm takes two steps to divide one of its inputs in half." However, I was having problems re-producing this argument.
So far this is what I have.
let $a_t$ and $b_t$ be the input to our gcd(a,b) program at iteration t (i.e. $\gcd(a_t,b_t)$. I have that after two iteration we have done:
$\gcd(a_t, \ b_t)$
$\gcd(a_{t+1}, \ b_{t+1}) = \gcd(b_t, \ a_t \pmod {b_t}) = \gcd(b_t, a_t - q b_t)$
$\gcd(a_{t+2}, \ b_{t+2}) = \gcd(a_t \pmod {b_t} , \ b_t \pmod {(a_t - q b_t)})$
And if one thinks in terms of bits, if $b_t$ is a power of 2, say $b_t = 2^k$, then after two steps the mod clear at least k bits from the n bit of $a_t$ to the k+1th bit of $a_t$. So for $a_{t+2}$ a bunch of higher order bits have been cleared. If we compare doing that to bit-shifting only by one bit to the right (i.e. dividing by 2), that only clears at most 1 bit, which means that after two operations, gcd at least halfs $a_t$. Which means that it clears a bit every two operations, so the run time should take worst-case 2n (if only manages to clear 1 bit every 2 iterations). However, this argument only works is $b_t$ is a power of 2 and it doesn't feel "rigorous" enough or solid enough, anyone know what I am missing?
Thanks in advance!

REPLY [2 votes]: Here's one way of looking at it: WLOG, assume that $a_0\gt b_0$; then one step of the algorithm takes $(a_0, b_0)\mapsto (a_1, b_1) = (b_0, a_0\bmod b_0)$.  Now, we can break into two cases: either $b_0\leq \frac{a_0}2$ or $b_0\gt \frac{a_0}2$.
If $b_0\leq\frac{a_0}2$, then we have by definition $a_1\leq \frac{a_0}2$, and since $b_1\leq a_1$ then $b_1\leq\frac{a_0}2$.
On the other hand, if $b_0\gt\frac{a_0}2$, we have $b_1 = a_0\bmod b_0 = a_0-b_0$ since $b_0\lt a_0 \lt 2b_0$; and because $b_0\gt \frac{a_0}2$, $b_1=a_0-b_0\lt\frac{a_0}2$.
In either case, since $a_2=b_1$ then we have that $a_2\leq\frac{a_0}2$; therefore the larger input must be divided at least by two every two steps.  This is enough to show that the algorithm takes $O(\log n)$ steps to find the GCD of two numbers $\leq n$, though of course this analysis is too coarse to give the correct leading constant.


TITLE: Derivation of Kolmogorov Forward Equation
QUESTION [0 upvotes]: By Ito's formula we have that for any suitable function $v(t,x)$,
$$
v(T, X_T) = v(t,X_t) + \int_t^T\left( v_s(s, X_s)+ b(s, X_s)v_x(s,X_s)+\frac{1}{2}\sigma^2(s, X_s)v_{xx}(s, X_s) \right)ds+\int_t^T\sigma(s, X_s)v_x(s, X_s)dW_s
$$
where $X_t$ satisfies the SDE,
$$
dX_t=b(t, X_t)dt + \sigma(t, X_t)dW_t
$$
Taking expectations conditional on $X_t =x$ we have,
$$
\mathbb E_t(v(T, X_T))-v(t, x)=\int_t^T\mathbb E_t\left( v_s(s, X_s)+ b(s, X_s)v_x(s,X_s)+\frac{1}{2}\sigma^2(s, X_s)v_{xx}(s, X_s) \right)ds
$$
Let $v(t, x)=0$ and $v(s, x) \to 0 $ as $ s \to T $, uniformly in x. Then,
$$
0=\int_t^T\mathbb E_t\left( v_s(s, X_s)+ b(s, X_s)v_x(s,X_s)+\frac{1}{2}\sigma^2(s, X_s)v_{xx}(s, X_s) \right)ds
$$
Now write in terms of the transition density and integrate by parts twice to get that the density $p(t, x;T, y )$ satisfies,
$$
\frac{\partial p}{\partial T} + \frac{\partial (bp)}{\partial y} - \frac{1}{2}\frac{\partial^2(\sigma^2 p)}{\partial y} = 0
$$
I'm not sure how proceed with the integration by parts step, which would start with something like this?
$$
\int_t^T\mathbb \int_{-\infty}^{\infty}\left( v_s(s, X_s)+ b(s, X_s)v_x(s,X_s)+\frac{1}{2}\sigma^2(s, X_s)v_{xx}(s, X_s) \right)p(s, x)\ dx\ ds
$$
How does partial differentials with respect to T and y come out from integrating this, can someone kindly enlighten ?
Thanks!

REPLY [1 votes]: I think one of the ways to proceed is as follows...
We consider each of the three terms inside the integrals separately (suppressing arguments) and we have,
$$
\begin{align}
 I_1 & = \int_t^T\mathbb \int_{-\infty}^{\infty} v_sp\ dx\ ds\\
& = \int_{-\infty}^{\infty} \left[ \left. vp\right|_{t}^{T}-\int_t^T vp_s\ ds\right] dx\\
I_2 & = \int_t^T\mathbb \int_{-\infty}^{\infty} bv_xp\ dx\ ds\\
& = \int_{t}^{T} \left[ \left. bvp\right|_{-\infty}^{\infty}-\int_{-\infty}^\infty v\frac{\partial{(bp)}}{\partial x}\ dx\right] ds\\
I_3 & = \int_t^T\mathbb \int_{-\infty}^{\infty} \frac{1}{2}\sigma^2v_{xx}p\ dx\ ds\\
& = \int_{t}^{T} \left[ \left. \frac{1}{2}\sigma^2v_xp\right|_{-\infty}^{\infty}-\int_{-\infty}^\infty \frac{1}{2}v_x\frac{\partial{(\sigma^2p)}}{\partial x}\ dx\right] ds\\
& = \int_{t}^{T} \left[ \left. \frac{1}{2}\sigma^2v_xp\right|_{-\infty}^{\infty}-\left[  \left. \frac{1}{2}v\frac{\partial{(\sigma^2p)}}{\partial x}\right|_{-\infty}^{\infty}\ -\int_{-\infty}^\infty \frac{1}{2}v\frac{\partial^2{(\sigma^2p)}}{\partial x^2} dx\right]\right] ds
\end{align}
$$
If by suitable choice of $v(t, x)$ we choose the class of functions with compact support ( and with earlier conditions ), all the terms with $\left. \right|_{-\infty}^{\infty}$ in $I_1, I_2, I_3$ vanishes and we get,
$$
\begin{align}
0 &=\int_t^T \int_{-\infty}^{\infty}vp_s\ dx\ ds + \int_t^T \int_{-\infty}^\infty v\frac{\partial{(bp)}}{\partial x}\ dx\ ds - \int_t^T \int_{-\infty}^\infty \frac{1}{2}v\frac{\partial^2{(\sigma^2p)}}{\partial x^2} dx\ ds\\
& = \int_t^T \int_{-\infty}^{\infty}v \left[ \frac{\partial p}{\partial s }+ \frac{\partial{(bp)}}{\partial x}-\frac{1}{2}\frac{\partial^2{(\sigma^2p)}}{\partial x^2}\right] dx\ ds
\end{align}
$$
Since $v(t, x)$ is arbitrary it means that we must have ( after renaming variables ),
$$
\frac{\partial{p}}{\partial T} + \frac{\partial{(bp)}}{\partial y}-\frac{1}{2}\frac{\partial^2{(\sigma^2p)}}{\partial y^2} = 0
$$
which gives the Kolmogorov Forward Equation


text:
\begin{document}
\bibliographystyle{plain}
\title{ Deterministic Sampling of Sparse Trigonometric Polynomials \thanks{
 Project supported by the Funds for Creative Research Groups of China (Grant No. 11021101)
and by NSFC grant 10871196 and National Basic Research Program of China (973 Program
2010CB832702) }}

\author{ \ Zhiqiang Xu}

\maketitle

\begin{abstract}
One can recover sparse multivariate trigonometric polynomials from
few randomly taken samples with high probability (as shown by Kunis and Rauhut). We give a deterministic sampling
of multivariate trigonometric polynomials inspired by Weil's exponential sum.  Our sampling can produce a deterministic matrix satisfying the statistical
 restricted isometry property, and also nearly optimal Grassmannian frames.
We show that  one can exactly reconstruct every $M$-sparse multivariate
trigonometric polynomial with fixed degree and of length $D$ from the
determinant sampling $X$, using the orthogonal matching pursuit, and $|X|$ is a
prime number greater  than $(M\log D)^2$. This result is optimal within the $(\log D)^2 $ factor. The simulations show that the
 deterministic sampling can offer reconstruction  performance similar to the random sampling.
\end{abstract}

\section{Introduction}

We investigate the problem of reconstructing sparse multivariate
trigonometric polynomials from few samples on $[0, 1]^{d}$. Let
$\Pi_q^d$ denote the space of all trigonometric polynomials of
maximal order $q\in \N$ in dimension $d$. An element  $f$ of
$\Pi_q^d$ is of the form
$$
f(x)\,\,=\!\!\sum_{k\in [-q,q]^d\cap \Z^d} c_k e^{2\pi ik\cdot x}, \quad x\in
[0,1]^d,
$$
where $c_k\in \C$. The dimension of $\Pi_q^d$ will be denoted by
$D:=(2q+1)^d$.
 We denote the support of the sequence of coefficients
of $c_k$ by $T$, i.e.,
$$
T:=\{k:c_k\neq 0\}.
$$
Throughout this paper, we will mainly deal with ``sparse"
trigonometric polynomials, i.e., we assume that  $|T|$ is much
smaller than the dimension of $D$ of $\Pi_q^d$. We set
$$
\Pi_q^d(M) := \bigcup_{T\subset [-q,q]^d\cap \Z^d\atop |T|\leq M} \Pi_T,
$$
where, $\Pi_T$ denotes the space of all trigonometric polynomials
whose coefficients are supported on $T$. Note that the set $\Pi_q^d(M)$  is the union of linear spaces and  consists of all trigonometric polynomials whose Fourier coefficients are supported
on a set $T\subset [-q,q]^d\cap \Z^d$ satisfying $|T|\leq M$.
 The aim of the paper is to sample
a trigonometric polynomial $f\in \Pi_q^d(M)$ at $N$ points and try to
reconstruct $f$ from these samples. We denote the sampling set
$$
X:=\{x_1,\ldots,x_N\}.
$$
We would like to reconstruct $f\in \Pi_q^d(M)$ from its sample
values
$$
y=f(x), \quad x\in X.
$$
 We use a  decoder $\Delta$ that maps
from $\C^N$ to $\Pi_q^d$, and the role of $\Delta$ is to provide an
approximation  to  $f$.
 The previous work concerns on the randomly taken samples. In \cite{tao1,tao2}, the authors choose $X$ by takeing  samples randomly on a lattice  and
use the {\em Basis Pursuit} (BP) as the decoder $\Delta$. In
\cite{trig1}, the result is generalized  for the case of
$x_1,\ldots,x_N$ being the uniform distribution on
$[0,1]^d$. We state the result as follows:
\begin{thm}\cite{trig1} Assume $f\in \Pi_q^d(M)$ for some
sparsity $M\in \N$. Let $x_1,\ldots,x_N\in [0,1]^d$ be
independent random variables having the uniform distribution on
$[0,1]^d$. If for some $\epsilon>0$ it holds
$$
N\geq CM\log(D/\epsilon)
$$
then with probability at least $1-\epsilon$ the trigonometric
polynomial $f$ can be recovered from its sample values $f(x_j)$,
$j=1,\ldots,N$, by Basis Pursuit. The constant $C$ is absolute.
\end{thm}

In \cite{trig2}, one chooses $\Delta$ as Orthogonal Matching Pursuit (Algorithm 1) and $X$ is
chosen according to one of two probability models:

(1) The sampling points $x_1,\ldots,x_N$ are independent random
variable having the uniform distribution on $[0,1]^d$;

(2) The sampling points $x_1,\ldots,x_N$ have the uniform
distribution on the finite set $2\pi\Z_m^d/m$ for some $m\in
\N\setminus \{1\}$.

\begin{thm}\label{th:trig2}\cite{trig2} Let $X=(x_1,\ldots,x_N)$ be chosen according to one of two probability models. Suppose that
$$
N\geq CM^2\log (D/\epsilon).
$$
 Then, with probability at least $1-\epsilon$, OMP recovers every $M$-sparse trigonometric polynomial. The constant $C$ is absolute.
\end{thm}

\begin{algorithm}
\begin{algorithmic}
 \STATE {\bf Input:}  sampling matrix ${\mathcal F}_X$, sampling vector $y=(f(x_j))_{j=1}^N$, maximum allowed sparsity $M$ or residula tolerance  $\epsilon$
 \STATE {\bf
Output:} the Fourier coefficients $c$ and its support $T$.
 \STATE {\bf Initialize:} $r^0=y,c^0=0,\Lambda^0=\emptyset, \ell=0$.
  \WHILE { $\|r^\ell\|_2>\epsilon$ or $\ell<M$}
  \STATE {\bf match:} $h^\ell={\mathcal F}_X^Tr^\ell$
  \STATE{\bf identity:} $\Lambda^{\ell+1}=\Lambda^\ell\cup\{{\rm argmax}_j|h^\ell(j)|\}$
  \STATE{\bf update:}  $c^{\ell+1}={\rm argmin}_{z: {\rm supp}(z)\subset \Lambda^{\ell+1}}\|y-{\mathcal F}_Xz\|_2$
  \STATE \,\,\qquad\qquad $r^{\ell+1}=y-{\mathcal F}_Xc^{\ell+1}$
  \STATE \,\,\qquad\qquad $\ell=\ell+1$
 \ENDWHILE
\end{algorithmic}
\caption{\small{Orthogonal Matching Pursuit}}
\end{algorithm}

The aim of this paper are twofold. First, we present  a deterministic sampling $X$   and
show   that OMP can recover every $f\in \Pi_q^d(M)$ exactly using
 $X$ with $|X|$ being a prime number greater  than $C(M\log D)^2$, provided $q$
 is fixed. So, we improve Theorem \ref{th:trig2}.
  Second, we construct a StRIP matrix with large range size.
 In particular, we exploit the connections between the exponential sum and the RIP matrix.

We now discuss the organization of this paper and we summarize its
main contributions. In Section 2, we introduce the deterministic
sampling and show that the coherence of the corresponding  sampling matrix less or
equal to  $ {(d-1)}/{\sqrt{N}} $ provided $N\geq 2q+1$
 and $N$ is a prime number. As a conclusion, OMP algorithm can  recover $f\in
\Pi_q^d(M)$ exactly when $N\geq  (d-1)^2 (2M-1)^2+1$ with the additional assumption of $N$ being prime number not less than $2q+1$. One has shown that if
$N\leq CM^{3/2}$, then with high probability there exists an
$M$-sparse coefficient vector $c$ depending on the sampling set such
that OMP fails (one also believes that the bound can be improved to
$O(M^2)$ ) (see \cite{OMP}). So, if one requires exactly recover of
{\em all} sparse trigonometric polynomials from a single sampling
set $X$, within the factor $\log^2 D$, our
deterministic sampling size almost meets the optimal bound for $f\in
\Pi_q^d(M)$ where  $q$ is fixed and  $d$ is variable. In Section 3, we show
that the $N\times D$ determining sampling matrix obeys the
Statistical Restricted Isometry Property (StRIP) of order $O(N (\log
(D/N))^2/(\log D(\log N)^2))$.  Though there are many deterministic
 sensing matrixes satisfying the StRIP \cite{quad,strip1},  the restriction to
 the size of our matrixes is light comparing with them.  Moreover,
 the StRIP matrix also implies nearly optimal Grassmannian frames. In Section 4, we  show that the
 deterministic sampling can provide similar reconstruction performance
 to that of the random ones by numerical experiments.

\section{Deterministic sampling}

\subsection{Exponential sums and sampling matrixes}
We first introduce a result in number theory, which plays a center role in our determinant sampling.
\begin{thm}\cite{weil}\label{th:weil} Suppose that $p$ is a prime number.
Suppose $f(x)=m_1x+\cdots+m_dx^d$ and there is a $j$, $1\leq j\leq d$,
so that $p\nmid m_j$. Then
$$
\left|\sum_{x=1}^p e^{\frac{2\pi i f(x)}{p}}\right|\,\, \leq\,\,
(d-1)\sqrt{p}.
$$
\end{thm}
We furthermore introduce the definition of {\em mutual incoherence}.
Let matrix $A=(a_1,\ldots,a_D)\in \C^{N\times D}$, where $N\leq D$
and $\|a_i\|_2=1$. The mutual incoherence of $A$ is defined by
$$
{\mathcal M}(A):=\max_{i\neq j}\left<a_i,a_j\right>.
$$
The low bound of ${\mathcal M}(A)$, which is also called as {\em
Welch's bound}, is given in \cite{welch}
\begin{equation}\label{eq:welch}
{\mathcal M}(A)\geq \sqrt{\frac{D-N}{(N-1)D}}.
\end{equation}
If the equality holds, we call $A$ as {\em optimal Grassmannian frames}. As shown in \cite{feichtinger},
 the equality can hold only if $D\leq N^2$ (see also \cite{mu}).
 Suppose that $N\geq 2q+1$ is a prime number.
We choose the sampling set $X=\{x_1,\ldots,x_N\}$ with
\begin{equation}\label{eq:x}
x_j= (j,j^2,\ldots,j^{d})/N \mod 1, \quad j=1,\ldots,N,
\end{equation}
 and denote by ${\mathcal F}_X$ the $N\times D$ {\em sampling matrix } with entries
$$
({\mathcal F}_{X})_{j,k} =\exp{(2\pi ik\cdot x_j)},\quad\quad\quad
j=1,\ldots,N,\,\, k\in [-q,q]^d.
$$
Also, $f(x_j)=({\mathcal F}_Xc)_j$, where $c$ is the
vector of Fourier coefficients of $f$. We let $\phi_k$ denote the
$k$-th column of ${\mathcal F}_X$. A simple observation is
$\|\phi_k\|_2=\sqrt{N}$. Set
$$\mu:={\mathcal M}({{\mathcal F}_X}/{\sqrt{N}}).$$
Then we have
\begin{lem}\label{le:co}
$$
\mu\,\,\leq\,\, {(d-1)}/{\sqrt{N}}.
$$
\end{lem}
\begin{proof}
Recall that $\phi_k$ denotes the $k$-th column of ${\mathcal F}_X$.
Note that
\begin{eqnarray*}
\left| \left<{\phi}_m,{\phi}_k\right>\right| = \left|\sum_{j=1}^N
e^{ 2\pi i p(j)/N}\right|,
\end{eqnarray*}
where $p$ is a polynomial with degree $d$ in the form of
$(m-k)\cdot (j,\ldots,j^{d})$ with $m,k\in [-q,q]^d$. Then Theorem \ref{th:weil} implies
that
$$
 \left| \left<{\phi}_m,{\phi}_k\right>\right|\,\, \leq \,\,
 (d-1)\sqrt{N}, \quad \mbox{\rm for   }\quad m\neq k.
 $$
Hence,
$$
\mu =\max_{m\neq k} \left<{\phi}_m,{\phi}_k\right>/N\,\,\leq\,\,
{(d-1)}/{\sqrt{N}}.
$$
\end{proof}
Let us consider recovery by OMP using the deterministic sampling $X$.
We first recall the following theorem:
\begin{thm}\cite{trig2}\label{th:omp} Assume $(2M-1)\mu <1$. Then OMP (and also
BP) recovers every $f\in \Pi_q^d(M)$.
\end{thm}
Combining Lemma \ref{le:co} and Theorem \ref{th:omp},  we have
\begin{thm}\label{th:main1}
Let  the sampling set $X=\{x_1,\ldots,x_N\}$ with
\begin{equation*}
x_j= (j,j^2,\ldots,j^{d})/N \mod 1, \quad j=1,\ldots,N.
\end{equation*}
Suppose $N \geq \max\{2q+1,(d-1)^2 (2M-1)^2+1\}$ and $N$ is a prime number. Then OMP (and also BP)
 recovers every $M$-sparse trigonometric polynomial exactly from the determinant sampling  $X$.
\end{thm}

\subsection{Special sparsity patterns}
For the deterministic sampling $X$, in Theorem \ref{th:main1}, an additional assumption is that $N\geq 2q+1=D^{1/d}$. Hence, only when  $q$ is fixed and $d$ is a variable,
we can say that $\max\{2q+1,(M(d-1))^2\}=O(M\log D)^2$.
However, if a prior information about the support of $f$ is known, the restriction might be reduced. For $\Gamma\subset [-q,q]^d\cap \Z^d$, recall that we use $\Pi_\Gamma$  to  denote the space of all trigonometric polynomials in dimension $d$ whose coefficients
 are supported on $\Gamma$.
 We let $\beta_\Gamma$ be the minimum constant so that, for any $k_1,k_2\in \Gamma$ with $k_1\neq k_2$, there exists a non-zero entry of the vector $k_1-k_2$,
 say $k_{1,j}-k_{2,j}$, such that $0<|k_{1,j}-k_{2,j}|\leq \beta_\Gamma$. Then, for $f\in \Pi_\Gamma$, we can replace the condition $N\geq 2q+1$ in Theorem \ref{th:main1}
 by $N\geq \beta_\Gamma+1$.  For example, we suppose that $\Gamma_0$ is a `curve' in $[-q,q]^d$, which is defined by
$$
\Gamma_0:=\left\{\left(m,\left\lfloor\frac{m}{(2q+1)^{1/d}}\right\rfloor,\ldots,\left\lfloor\frac{m}{(2q+1)^{(d-1)/d}}\right\rfloor\right): -q\leq m\leq q\right\}.
$$
Then a simple argument shows that $\beta_{\Gamma_0}\leq (2q+1)^{1/d}$. Hence, OMP can recover $M$-sparse trigonometric polynomials $f\in \Pi_{\Gamma_0}$ exactly from
 determinant sampling $X$ with $N \geq \max\{(2q+1)^{1/d},(d-1)^2 (2M-1)^2+1\}$ and $N$ being a prime number. In particular, if $d\geq \log_2(2q+1)$, the condition
  $N\geq (2q+1)^{1/d}$ is reduced to $N\geq 2$.

\subsection{ Related work } We are not the only ones seeking the deterministic Fourier
sampling. We would especially like to note works by Iwen
\cite{iwen1,iwen2,iwen3} and Bourgain et al \cite{erip}. In \cite{iwen1}, a deterministic Fourier sampling method is considered and a sublinear-time algorithm which recovers  one
dimensional sparse trigonometric polynomials $f$ is presented. However, the sampling in
\cite{iwen1} need a combinatorial structure, which seems  non-trivial to be constructed. Moreover, the coherence of the sampling matrix in
\cite{iwen1} is not small. In recent work
 \cite{iwen2,iwen3}, Iwen presents a binary matrix, say ${\mathcal B}$,
with small coherence. By computing the product of ${\mathcal B}$ and the
discrete Fourier matrix $\Psi$, one can obtain a deterministic  sampling matrix
${\mathcal B}\cdot \Psi$. However, the construction
 of ${\mathcal B}$ requires $O(M\log D)$ large primes and one also needs a fast algorithm for computing the product of ${\mathcal B}$ and $\Psi$.

Our work is in a different direction.  The main concern of our methods is to
present a determinist sampling with an {\em analytic form} so that the
coherence of the sampling matrix is as small as possible and hence the popular
decoder algorithms, such as OMP and BP, can work well for the sampling. In
fact, to construct our deterministic sampling, we only require a prime number
$N$. The coherence of our deterministic sampling matrix almost meets the Welch's
bound. Hence, we also present a nearly optimal harmonic Grassmannian frames,
which may be of independent interest \cite{mu}. We also point out another
difference between our study and that of Iwen. The deterministic sampling given
in \cite{iwen1,iwen2,iwen3} is designed for trigonometric polynomials in a
single variable.   In \cite{iwen3}, the author shows that one can deal with
high dimensional trigonometric polynomials by a dimensionality reduction
technique, but it requires the integer solutions of a linear equation and hence
it is an indirectly method.  In contrast, our sampling is much more convenient
for dealing with high dimensional trigonometric polynomials. The last, but not
 least,  it seems that in practice the algorithms given in \cite{iwen1,iwen3} require
much more samples than OMP and BP when the dimension $d$ is large.

We next compare our study and that of Bourgain et al. In \cite{erip}, for the case with $d=1$, Bourgain et al show a connection between the deterministic Fourier sampling and Tur\'{a}n's problem, and also present many possible approaches to constructing the sampling. Comparing with the approaches given in \cite{erip}, our sampling has the advantage of simplicity. Another important distinction is that our sampling strategy can be interpretable as a sampling strategy for recovering higher dimensional sparse trigonometric polynomials.

Finally, we would like to point out connections with chirp sensing codes.
In \cite{chirp}, a $N\times N^2$ measurement matrix $\Theta$ is designed with chirp sequences forming the columns, i.e.,
$$
(\Theta)_{\ell,k}=\exp(2\pi i r \ell ^2/N) \exp(2\pi i m \ell/N) \, \text{ with } 1\leq \ell \leq N \text{ and } k=Nr+m, 1\leq k \leq N^2.
$$
If we take $d=2$, then ${\mathcal F}_{X}$ is reduced to the chirp sensing matrix $\Theta$. Hence, the measurement matrix $\Theta$ can be considered
 as a special case of our determinant sampling matrix ${\mathcal F}_X$. Noting that the coherence of the matrix ${\mathcal M}(\mathcal F_X/\sqrt{N})$ is not more than $(d-1)/\sqrt{N}$, by an argument   similar to one employed by DeVore in \cite{devore}, we can show that $\mathcal F_X/\sqrt{N}$ satisfies RIP of order $k$ with constant $\delta=(k-1)(d-1)/\sqrt{N}$   (the definition of RIP is given in the next section). For fixed $0<\delta <1$, we can obtain the up bound $k=O(\sqrt{N}/d)$. Using the method of additive combinatorics, in \cite{erip}, Bourgain et al investigate the RIP property of $\Theta$ and show that one can construct  $N\times D$ RIP matrixes of order
    $k$ with $N=o(k^2)$, which implies that a better up bound of $k$. It will be a challenging  problem to extend the result  in \cite{erip} to the matrix ${\mathcal F}_X$.
\section{RIP and StRIP}

Given a $N\times D$ matrix $\Phi$ and any set $T$ of column indices,
we denote by $\Phi_T$ the $n\times |T|$ matrix composed of these
columns. Similarly, for a vector $y\in \C^D$, we use $y_T$ to denote
the vector formed by the entries of $y$ with indices from $T$.
Following Cand\`{e}s and Tao, we say that $\Phi$ satisfies the
Restricted Isometry Property (RIP) of order $k$ and constant $\delta
\in (0,1)$ if
\begin{equation}\label{eq:con}
(1-\delta) \|y_T\|^2 \leq \|\Phi_Ty_T\|^2 \leq (1+\delta) \|y_T\|^2
\end{equation}
holds for all sets $T$ with $|T| \leq k$.
 In fact, (\ref{eq:con}) is equivalent to requiring that the
 Grammian matrices $\Phi_T^\top\Phi_T$ has all of its eigenvalues in $[1-\delta,
 1+\delta]$ for all $T$ with $|T|\leq k$.
 A fundamental question in compressed sensing is the construction of
suitable RIP matrix $\Phi$.
In general,  RIP matrices can be  constructed using random variables such as Gaussian or Bernoulli as  their entries.
However, the construction of the deterministic RIP matrices is a challenging task (see also \cite{devore,erip}).
Given that there are no satisfying deterministic construction of RIP matrices, several authors suggest  an alternative statistical version of  RIP \cite{quad,strip2}:
\begin{defn}  We say that a deterministic matrix
$\Phi$ satisfies statistical restricted isometry property (StRIP) of order $k$ with constant $\delta$ and
probability $1-\epsilon$ if
$$
{\rm Pr}(\left| \|\Phi y\|^2-\|y\|^2\right|\leq \delta\|y\|^2)
\geq 1-\epsilon,
$$
with respect to a uniform distribution of the vectors $y$ among all $k$-sparse
vectors in $\R^D$ of the same norm.
\end{defn}
In \cite{strip1}, the authors derive the StRIP performance bound in
terms of the mutual coherence of the sampling matrix and the
sparsity level of input signal, as summarized by the following
theorem:
\begin{thm} \cite{strip1}\label{th:th32}
Let $\Phi=(\phi_1,\ldots,\phi_D)$ be an $N\times D$ deterministic
 matrix, where each column has unit norm. Assume further
that all row sums of $\Phi$ are equal to zero, and ${\mathcal M}(\Phi)\leq
\alpha_1/\sqrt{N}$, where  $\alpha_1$ is some constant.  Then $\Phi$ is a StRIP of order
$k\leq c_0(\delta)N/\log D$ with constant $\delta$ and probability
$1-1/D$, where $c_0(\delta)=\delta^2/(8\alpha_1^2)$.
\end{thm}
As stated in \cite{quad,strip1,strip2}, there are a large class of
deterministic matrices which satisfy the StRIP. However, the
restriction on the size ($N$ and $D$) is heavy. For example, FZC
Codes \cite{fzc} require that $D=N^2$ and $N$ is a prime number;
Gold/Gold-like Codes \cite{gold} require that $D=(N+1)^2$ and $N$ is
in the form of $2^p-1, p\in \Z$, and so on. We next construct a
deterministic  StRIP  matrix with the large  range size
 based on the method introduced in Section 2.

Suppose $N\in \N$ is a prime number. We suppose that $D\in \N$
can be written in the form of  $D=p_1\cdots p_d$, where $N=p_1\geq
p_2\geq \cdots \geq p_d\geq 2$ and $p_1,\ldots, p_d$ are prime numbers.
For $t=1,\ldots,d$, we set
$$
I_t:=
\begin{cases}
[-(p_t-1)/2,(p_t-1)/2] ,\,\,\, p_t\neq 2,\\
[0,1], \,\,\, p_t=2.
\end{cases}
$$
Recall that
$$
{x}_j= (j,j^2,\ldots,j^{d})/N \mod 1, j=1,\ldots, N,
$$
and denote by $\tilde{\mathcal F}_X$ the $N\times D$ matrix with
entries
$$
(\tilde{\mathcal F}_{X})_{j,k} =\exp{(2\pi ik\cdot
{x}_j)},\quad j=1,\ldots,N,\,\, k\in I_1\times I_2 \times
\cdots \times I_d.
$$
\begin{thm}\label{th:33}
Suppose that $0<\delta<1$ is given. The matrix $\tilde\Phi:=\tilde{\mathcal F}_{X}/\sqrt{N}$ is a StRIP of order $\delta^2
\frac{N}{8(\log D)}\left(\frac{\log (D/N)}{\log N}\right)^2$ with constant $\delta$ and
probability $1-1/D$.
\end{thm}
\begin{proof} We denote the  mutual coherence of $\tilde{\Phi}$ by $\tilde\mu$. Using the same method with the proof of Lemma \ref{le:co},
 we obtain that $\tilde\mu \leq (d-1)/\sqrt{N}$. Note that the all row sums of $\tilde{\mathcal F}_{X}$  is $0$, and also
  that $(d-1)^2 \geq \left(\frac{\log N}{\log (D/N)}\right)^2$. The conclusion can follow from Theorem \ref{th:th32} directly.
\end{proof}
\begin{remark} When $D\gg N$, the Welch's bound (\ref{eq:welch}) approximately equals to $1/\sqrt{N}$. Note that
$$
{\mathcal M}(\tilde{\Phi})\leq (d-1)/\sqrt{N} \leq \log_2D/\sqrt{N}.
$$
The mutual incoherence of $\tilde\Phi$ almost meets the Welch's bound, which implies that $\tilde\Phi$ is a nearly optimal harmonic Grassmannian frame (see \cite{mu}).
\end{remark}
\section{Numerical Experiments}

The purpose of the experiment is the comparison for the random
sampling and the determinant sampling.  Given  the degree of
trigonometric polynomials $q\in \N$ and the number of variables
$d\in \N$, the support set $T$ is drawn from the uniform
distribution over the set of all subsets of $[-q,q]^d$ of size $M$.
The non-zero Fourier coefficients, the real as well as the imaginary
part of $c_j, j\in T$, have the Gaussian distribution with mean zero
and standard deviation one. For the determinant sampling, we use the
method introduced in Section 2 to produce the sampling  points $x_j,j=1,\ldots,N$.
Similar with \cite{trig2},  we choose the random sampling points based on the continuous probability model.

\begin{example}
We take $q=2, d=5, D=3125$ and draw a set $T$ of size $M\in
\{1,2,\ldots,40\}$. The $N=83$ deterministic sampling points are obtained by the method introduced in Section 2, and the
random sampling points are produced by the continuous probability model.  We reconstruct the Fourier
coefficients by OMP  and BP, respectively. In \cite{trig2}, the complexity of OMP is analysised
 in detail. For BP, we use the optimization tools of CVX \cite{cvx}.   We repeat the experiment 100 times for each number $M$ and calculate the success rate.
 Figure 1  and Figure 2 depict the numerical results with the reconstructing algorithm OMP and BP, respectively.  From these, one can observe that
 the performance of deterministic sampling is very similar to those of the random sampling. The numerical experiments imply the promising application of the deterministic sampling.

\begin{figure}[h]
\begin{minipage}[t]{0.51\linewidth}
\centering {
\includegraphics[width=\textwidth]{omp.eps}
\caption{ Simulation results using \newline the OMP } }
\end{minipage}
\hfill
\begin{minipage}[t]{0.51\linewidth}
\centering
\includegraphics[width=\textwidth]{l1.eps}
\caption{Simulation results using\newline the BP\label{your label}}
\end{minipage}
\end{figure}

\end{example}

\begin{example}
As said before, RIP of order $k$ with constant $\delta$ is equivalent to requiring that the
 Grammian matrices $\Phi_T^\top\Phi_T$ has all of its eigenvalues in $[1-\delta,  1+\delta]$ for all $T$ with $|T|\leq k $.
So, the purpose of the second experiment is the comparison for the maximum and minimum eigenvalue statistics of
 Gram matrices $\Phi_T^\top\Phi_T$ of varying sparsity $M:=|T|$ for deterministic sampling matrix and random sampling matrix.
  In order to do this, for every value $M$, sets $T$ are drawn uniformly random over all sets and the statistics are accumulated
  from 50,000 samples. Figure 3 shows the sample means of the maximum and minimum eigenvalues of $\Phi_T^\top\Phi_T$ for  $M\in \{1,\ldots,20\}$.
   \begin{figure}
\begin{center}
\epsfxsize=6cm\epsfbox{eig.eps} \caption{Eigenvalue statistics of
Gram matrices $\Phi_T^\top\Phi_T$ for deterministic sampling matrixes
and random sampling matrixes }
\end{center}
\end{figure}
\end{example}

\bigskip
{\bf Acknowledgments.} We would like to thank the referees for valuable comments on this paper.

\bigskip

config: arxiv


TITLE: Interlacing two ordered sequences with constraints
QUESTION [1 upvotes]: How many ways can we create a sequence of length $2n$ from $\{x_i\}_{i=1}^n$ and $\{y_j\}_{j=1}^n$ so that  $x_1<x_2<\cdots <x_n$,
 $\;y_1<y_2<\cdots <y_n$ and
 $x_i<y_i$ for all $1\leq i\leq n$ ?
This question is related to the following
enter link description here, but with an extra condition on the ordering between the two sequences.
Using the wordings in the original question: Suppose we have two finite, ordered sequences $x=(x_1,\cdots,x_n)$ and $y=(y_1,\cdots,y_n)$. How many ways can we create a new sequence of length $2n$ from $x$ and $y$ so that the order of elements is preserved AND we have orderings $(x_i,y_i)$ for all $i$?

REPLY [1 votes]: The Catalan number.
If a's are left parentheses and b's are right parentheses, the condition translates into "there are less then i right parentheses to the left of the i-th left parenthesis".
e.g. For n = 3 we have
$(\ )(\ )(\ ),\ (\ )((\ )),\ ((\ ))(\ ),\ ((\ )(\ )),\ (((\ )))$ or
$a_1b_1a_2b_2a_3b_3,\ a_1b_1a_2a_3b_2b_3,\ a_1a_2b_1b_2a_3b_3, \ a_1a_2b_1a_3b_2b_3,\ a_1a_2a_3b_1b_2b_3$


TITLE: How much different between $D_{KL}[P(X)||Q(X)]$ and $D_{KL}[Q(X)||P(X)]$?
QUESTION [1 upvotes]: While Kullback Leibler divergence is not symmetric: $D_{KL}[P(X)||Q(X)] \neq D_{KL}[Q(X)||P(X)]$, how much different $D_{KL}[P(X)||Q(X)]$ from $D_{KL}[Q(X)||P(X)]$?
Does the quantity $D_{KL}[P(X)||Q(X)] - D_{KL}[Q(X)||P(X)]$ have some interesting interpretation?

REPLY [1 votes]: Let $\epsilon \in (0,1)$ and suppose that $P(X)=(1-\epsilon)\delta_{0}+\epsilon\delta_{1}$ and $Q(X)=\frac 12\delta_{0}+\frac 12\delta_{1}$.
Then $D_{KL}[P(X)||Q(X)]=(1-\epsilon)\ln(2(1-\epsilon))+\epsilon \ln(2\epsilon)$ and $$D_{KL}[Q(X)||P(X)] = \frac 12 \ln(\frac 1{2(1-\epsilon)})+\frac 12\ln(\frac{1}{2\epsilon})$$
As $\epsilon \to 0$, $D_{KL}[P(X)||Q(X)]\to \ln 2$ and $D_{KL}[Q(X)||P(X)] \to \infty$, thus $$D_{KL}[P(X)||Q(X)] - D_{KL}[Q(X)||P(X)] \xrightarrow[\epsilon \to 0]{}-\infty$$
The rationale is that the KL divergence $D_{KL}[\mu||\nu]$ blows up when $\mu$ is not absolutely continuous w.r.t $\nu$ (e.g. when the support of $\mu$ is not a subset of the support of $\nu$). This is a common pitfall for $f$-divergences.


text:
\vspace{-2.5ex}
\section{Discussion}
\label{sec:conclusion}
\vspace{-1ex}
When training over-parameterized models in the interpolation setting, we showed that for smooth, convex functions, constant step-size variants of both \adagrad/ and \amsgrad/ are guaranteed to converge to the minimizer at $\bigO(1/T)$ rates. We proposed to use stochastic line-search techniques to help these methods adapt to the function's local smoothness, alleviating the need to tune their step-size and resulting in consistent empirical improvements across tasks. Although adaptive gradient methods outperform SGD in practice, their convergence rates are worse than constant step-size SGD and we hope to address this discrepancy in the future.


TITLE: Is Complex Numbers the biggest field? If yes, is there any easy proof to understand it?
QUESTION [5 upvotes]: Is the Complex Numbers the biggest field?
If yes, does anyone have a "simple"/"easy to understand" proof?

REPLY [11 votes]: It depends on your notion of "biggest". The complex numbers aren't the biggest field in the sense that you could adjoin a new variable to them, say $\mathbb{C}(x)$, and obtain a new field into which $\mathbb{C}$ sits embedded as a subfield. They also aren't the biggest field in terms of cardinality, since you could probably put field structures on sets of arbitrarily large cardinalities.
But they are biggest, in the sense they are algebraically closed. This means that if you try to adjoin a new element to them that satisfies some polynomial relation, you... can't. The variable $x$ in $\mathbb{C}[x]$ doesn't satisfy any relations, so this extension isn't algebraic. But something like $\mathbb{C}[x]/{(3x^2 + 1)}$, where we add in a "new" thing $\alpha$ satisfying the polynomial equation $3\alpha^2 + 1 = 0$, is an algebraic extension. But you know that every complex polynomial has a root, so we can't add in this $\alpha$ to $\mathbb{C}$ - it's already there. On the other hand, $\mathbb{R}[x]/{(3x^2 + 1)}$ is "bigger" than $\mathbb{R}$ since we added in a new thing - a solution to $3\alpha^2 + 1 = 0$. This didn't already live in $\mathbb{R}$, so adding this thing actually extends the field.

REPLY [7 votes]: It depends on the interpretation of the word 'biggest'. There are certainly fields of larger cardinality than $\mathbb C$ that contain $\mathbb C$ (for instance, take any set $S$ and consider the field $\mathbb C(S)$ where the elements of $S$ are adjoined as independent transcendental elements). So, if you measure size by cardinality, then for every field $\mathbb F$ there is a larger field containing it, and thus, in particular, $\mathbb C$ is not largest.
However, if by biggest you mean that every polynomial over it has a root in it, in other words being algebraically closed, then $\mathbb C$ is well-known to be algebraic closed and thus in that sense $\mathbb C$ is the largest algebraic extension of $\mathbb R$.