\section{Outlook and Future Work}
In this paper we have studied the reconstruction of a binary, sparse signal $x_0\in \{0,1\}^N$ from biased partial random circulant and Toeplitz measurements $y=Ax_0 +n$, where $n$ is some small noise vector and $A=\Phi(b)+\mu\one$. Here, $\Phi(b)$ a partial random circulant or Toeplitz matrix and $b$ is a sub-Gaussian vector.
In particular, we have studied the reconstruction via basis pursuit with box constraints and linear least squares with box constraints. Surprisingly, we could prove that the least squares algorithm, which usually does not promote sparsity, works comparably well. We further showed that we need as many measurements to recover an $s$-sparse signal as we need to recover an $(N-s)$-sparse signal and that this number is about $\min\{s,N-s\}\log{N}$. Finally we substantiated our theory by some numerical simulations.

The numerical simulations further indicate that, as for non-structured sub-Gaussian measurements, the number of necessary measurements $M$ to ensure unique recovery (independently of the sparsity) is not larger than $M=N/2$. In the following we would like to explain some thoughts on this phenomenon and a possible proof of it.

In order to prove the mentioned phenomenon, we would need to show that the measurement matrix $\Phi_{\Theta}$ is in general position and orthant symmetric; see the proof of Theorem III.2 in \cite{FlKei}, for comparison.


Note, that $\Phi_{\Theta}$ is in general position if for every subset $B\subset[N]$ of cardinality $|B|=M$ the eigenvalues of the matrix $(\Phi_\Theta^{B})^*\Phi_\Theta^B$ are positive, i.e., if $\lambda(\Phi_\Theta^{B})^*\Phi_\Theta^B)>0$ or $s_N(\Phi_\Theta^B)\ge0$, respectively, where $s_N(A)$ denotes the smallest singular value of a matrix $A\in \R^{N,N}$. Note that there exists a lot of work in the literature calculating the probability of $\lambda(\Phi^*\Phi)>0$ (\cite{Paulo, Gray}), but an analogous calculation for $\lambda((\Phi^{B})^*\Phi^B)$ is much more difficult. The main reason is that the eigenvalues of $\Phi$ itself can be computed very easily, which is not the case for a submatrix. In particular it has been shown in \cite{Paulo}, for Rademacher sequences $(b_0,\dots,b_{N-1})$ (among others) that for all $\varepsilon >0$ and large $N$
\begin{align}\label{eqn:EVCirc}
\prb{s_N(\Phi(b))\ge \varepsilon N^{-1}}\ge 1-C\varepsilon,
\end{align}
where $C>0$ is a constant only depending on $b$.
Since $\Phi^B_\Theta$ seems to be more unstructured than $\Phi$ itself one might hope that the probability of $\lambda((\Phi^{B}_\Theta)^*\Phi^B_{\Theta})>0$ is even higher.

However, the proof of Theorem III.2 in \cite{FlKei}, is also based upon the fact that the random part $\Phi$ of the measurement matrix $A=\mu \one +\Phi$ has an orthant symmetric kernel. This means, if for each diagonal matrix $S\in \R^{N,N}$ with diagonal in $\{-1,1\}^N$ and every measurable set $\Omega\in \R^{M,N}$, it holds $\prb{B S\in \Omega}=\prb{B\in \Omega}$, where $B$ is a matrix whose rows span the kernel of $\Phi$. 

From our point of view, it seems to be very unlikely that this is true for partial circulant matrices. The reason is the following. Suppose the kernel of $\Phi_{\Theta}$ is spanned by $v_1,\dots,v_m$, for some $m\in [N]$, and let $B\in \R^{m,N}$ the matrix with rows $v_1',\dots,v_m'$, then the rows of $BS$ span the kernel of $TS$. But $TS$ is in general no circulant marix. 

So for future work it is interesting to check if the kernel of a partial circulant matrix is indeed not or perhaps is orthant symmetric. Independently of the answer to this question it might be of own interest to prove an inequality in the spirit of \eqref{eqn:EVCirc} for partial circulant matrices. And, if the answer to the first question is negative, to find an alternative way to proof the upper bound on the necessary number of measurements in the order of $M\lesssim N/2$.
{"config": "arxiv", "file": "2006.14835/UpperBound.tex"}