# One-Bit Compressed Sensing via One-Shot Hard Thresholding

Jie Shen
Stevens Institute of Technology
New Jersey, USA
<EMAIL_ADDRESS>
###### Abstract

This paper concerns the problem of 1-bit compressed sensing, where the goal is
to estimate a sparse signal from a few of its binary measurements. We study a
non-convex sparsity-constrained program and present a novel and concise
analysis that moves away from the widely used notion of Gaussian width. We
show that with high probability a simple algorithm is guaranteed to produce an
accurate approximation to the normalized signal of interest under the
$\ell_{2}$-metric. On top of that, we establish an ensemble of new results
that address norm estimation, support recovery, and model misspecification. On
the computational side, it is shown that the non-convex program can be solved
via one-step hard thresholding which is dramatically efficient in terms of
time complexity and memory footprint. On the statistical side, it is shown
that our estimator enjoys a near-optimal error rate under standard conditions.
The theoretical results are substantiated by numerical experiments.

##  1 Introduction

The last two decades have witnessed a large demand of learning from high-
dimensional data where the number of attributes is of the same order of, or
even greater than the number of observations. Consider, for example, the Lou
Gehrig’s disease: there are millions of possible factors to evaluate but the
scientists have a very restricted number of samples for research (each year 2
out of 100,000 individuals are affected by it). It thus turns out to be
indispensable to investigate and to resolve two fundamental problems in this
scenario: a) when is it possible to learn a useful model from the small amount
of data; and b) how can we construct an accurate estimator with mild
computational overhead. Answering these two questions has become a central
theme in the field of high-dimensional statistics, and there have been a
fruitful literature in a variety of applications such as linear regression
[12, 34], classification [17], principal component analysis [23, 43],
precision matrix estimation [10], to name just a few.

As a special instance of linear regression, compressed sensing (CS) has
attracted increasing attention owing to its ease of implementation and the
success in practical problems [16]. To be more detailed, CS consists of two
phases: data acquisition and signal recovery. Suppose that
$\bar{\boldsymbol{x}}\in\mathbb{R}^{d}$ is the signal of interest. During the
first phase, the goal is to efficiently sample it and store the obtained
measurements in a device. In light of the fact that such a device may not be
computationally powerful, a common paradigm is to adopt linear measurements
which mitigate hardware implementation and accelerate data collection. That
is, we specify the number of measurements $n$ and the sensing vectors
$\\{\boldsymbol{a}_{i}\\}_{i=1}^{n}\subset\mathbb{R}^{d}$, and record in the
device the measurements $\\{y_{i}\\}_{i=1}^{n}$ given by

$y_{i}=\left\langle\boldsymbol{a}_{i},\bar{\boldsymbol{x}}\right\rangle,\
\forall\ i=1,\dots,n.$ (1.1)

For the purpose of efficient sampling, it is required that $n\ll d$, hence the
name compressed sensing.

During the second phase, one has access to
$\\{(\boldsymbol{a}_{i},y_{i})\\}_{i=1}^{n}$ and the primary concern is to
recover the underlying signal $\bar{\boldsymbol{x}}$ on a possibly powerful
machine. While (1.1) is an underdetermined linear system that might have
infinite number of feasible solutions, it has been well-understood that with a
careful design of the sensing vectors, a broad range of algorithms are capable
of producing accurate, or even exact reconstruction of $\bar{\boldsymbol{x}}$
in polynomial time provided that it exhibits certain low-dimensional
structure. See, for example, [11, 35, 38, 8, 31].

Though elegant in theory and compelling in practice, [9] pointed out that it
is not always realistic to collect the measurements as in (1.1) since they
entail infinite-bit precision for the hardware. Alternatively, the
measurements are often quantized into finite bits and in the extreme case,
only the sign patterns are retained:

$y_{i}=\operatorname{sign}\left(\left\langle\boldsymbol{a}_{i},\bar{\boldsymbol{x}}\right\rangle\right),\
\forall\ i=1,\dots,n.$ (1.2)

The problem of recovering $\bar{\boldsymbol{x}}$ from its binary measurements
is referred to as 1-bit compressed sensing, and it bears the potential of
savings of physical storage as long as accurate estimation in the 1-bit
setting does not require significantly more measurements [21]. Note that as
the sign function absorbs the magnitude of $\bar{\boldsymbol{x}}$, we can only
hope to reconstruct the direction
$\bar{\boldsymbol{x}}/\left\lVert\bar{\boldsymbol{x}}\right\rVert$ in general.
In this light, the research lines can be roughly divided into three spaces:
(a) sparse approximation, i.e. identifying the direction; (b) norm estimation,
i.e. evaluating the norm with extra information; and (c) support recovery,
i.e. determining the position of the non-zero entries of
$\bar{\boldsymbol{x}}$.

##### Sparse Approximation.

Perhaps surprisingly, it was provably shown in [25] that by seeking a global
optimum of $\ell_{1}$-norm constrained programs, it is possible to reliably
recover the underlying normalized signal with as many observations as in the
standard model (1.1). However, it comes up with a computational issue when
optimizing the programs over large-scale data sets. From a technical
perspective, since the programs are not strongly convex, only a sublinear
convergence rate is guaranteed for projected gradient descent [24]. In other
words, one has to run the algorithm for a considerable number of iterations in
order to attain the optimum. Therefore, a large body of works were dedicated
to investigating alternative programs that are endowed with closed-form
solutions, which naturally rules out the trouble of slow convergence. For
instance, [47] considered optimizing an $\ell_{1}$-norm penalized function
which is exactly the Lagrangian function of the program in [25].
Interestingly, with the slight modification, it was shown that a simple
element-wise thresholding on a certain vector gives even better error rate.
Yet, for the sake of accurate recovery, one has to search for a proper
regularization parameter which itself could be expensive. In particular,
specifying a large value for it will result in trivial statistical guarantee
whereas a small value will lead to a trivial solution (i.e. a zero vector).
[20] illustrated that one can derive closed-form solutions for other sparsity-
regularized programs such as smoothly clipped absolute deviation penalty [18],
minimax concave penalty [46], and $\ell_{0}$-norm (that counts the number of
non-zeros of a vector). Unfortunately, no statistical guarantee was
established in that work.

##### Norm Estimation.

While it seems implausible to evaluate the norm of $\bar{\boldsymbol{x}}$
under the 1-bit setting, a number of recent works asserted that the premise
quickly changes under extra conditions. For example, [22, 6] concurrently
showed that by manually adding Gaussian noise before quantization, one may
estimate the magnitude by solving an augmented program that incorporates the
noise information. This idea was further utilized to deal with heavy-tailed
sensing vectors in [15].

##### Support Recovery.

Parallel to the line of estimating the direction of the signal, a plethora of
works examined the problem of recovering the support set. In statistics, it is
also known as variable selection or feature selection [34, 39]. Note that
support recovery sheds light on sparse approximation in that once the support
is identified, we can safely eliminate the irrelevant features and apply
standard tools from regression theory (that has a rich literature).
Unfortunately, it is typically more challenging to establish theoretical
guarantee in this space even under the standard CS model [42, 29, 30]. In the
regime of 1-bit CS, [19, 1] presented a set of impressive results based on a
new family of sensing vectors that move away from the standard Gaussian. The
data acquisition is computationally more demanding though.

###  1.1 Our Contributions

We propose to study a sparsity-constrained non-convex program for the 1-bit CS
problem. We first demonstrate that the global optimum can be computed by a
simple hard thresholding operator (to be defined) which is computationally
efficient. More importantly, the solution is proved to have a near-optimal
approximation error rate to the direction of $\bar{\boldsymbol{x}}$. We
develop novel analysis showing that the approximation error is controlled by
two factors: one is independent of the signal structure while the other is
entirely determined by it. On top of that, we provide theoretical
justification that our estimator recovers the support set of
$\bar{\boldsymbol{x}}$, can be tailored to offer an accurate estimation of the
magnitude of $\bar{\boldsymbol{x}}$, and is resilient to model
misspecification. Namely, even when we feed an inappropriate parameter to the
program, our estimate still exhibits favorable performance.

###  1.2 Related Works

The 1-bit CS problem is closely related to learning halfspaces – a central
object of study in learning theory [36]. In compressed sensing, there is an
additional structural assumption that the halfspace is embedded in a high-
dimensional space, and at the heart of CS is leveraging such prior knowledge
for improved sample complexity. In view of the connection to learning theory,
a surge of recent works are devoted to understanding their interplay. For
example, active learning is a long-established research field in learning
theory, which attempts to mitigate the human labor for data annotation by
actively querying the labels [4, 41, 44, 45, 32]. Similar ideas are also
explored in CS, known as adaptive sensing [3, 6].

It is also worth mentioning that one can expand the observation model (1.2) to
1-bit matrix completion that has found successful applications in social
networks. For example, in recommender systems we can construct an incomplete
data matrix where each observed entry represents the preference (like or
dislike) of a user to an item [13, 40]. The goal is to predict the missing
entries and to recommend items that are potentially interesting for the
customers. The statistical guarantee for this problem has been established in
a series of appealing works [7, 28].

##### Notation.

We use bold lowercase letters such as $\boldsymbol{v}$ to denote a column
vector. Its $i$th element is denoted by $v_{i}$. There are three norms that
will be involved for a vector $\boldsymbol{v}\in\mathbb{R}^{d}$: the
$\ell_{2}$-norm
$\left\lVert\boldsymbol{v}\right\rVert:=\sqrt{v_{1}^{2}+\dots+v_{d}^{2}}$, the
$\ell_{1}$-norm $\left\lVert\boldsymbol{v}\right\rVert_{1}:=\left\lvert
v_{1}\right\rvert+\dots+\left\lvert v_{d}\right\rvert$, and the
$\ell_{\infty}$-norm
$\left\lVert\boldsymbol{v}\right\rVert_{\infty}:=\max_{1\leq i\leq
d}\left\lvert v_{i}\right\rvert$. We write the number of non-zero elements in
$\boldsymbol{v}$ as $\left\lVert\boldsymbol{v}\right\rVert_{0}$, and with a
slight abuse of terminology we will call it
$\ell_{0}$-norm111$\left\lVert\boldsymbol{v}\right\rVert_{0}$ is not a norm as
it is not absolutely homogeneous..

For a finite set $\mathcal{S}$, its cardinality is denoted by
$\left\lvert\mathcal{S}\right\rvert$. The index set of the non-zero elements
of a vector $\boldsymbol{v}\in\mathbb{R}^{d}$ is called the support set, and
is denoted by $\operatorname{supp}\left(\boldsymbol{v}\right)$. We write the
index set of the top $k$ elements (in magnitude) as
$\operatorname{supp}\left(\boldsymbol{v},k\right)$ with ties being broken
lexicographically.

We reserve $\bar{\boldsymbol{x}}$ for the $s$-sparse target signal that we
hope to estimate. We also reserve the upright capital letter $\mathrm{{C}}$
and its subscript variants such as $\mathrm{{C}}_{0}$ and $\mathrm{{C}}_{1}$
for absolute constants, whose values may change from appearance to appearance.
For two scalars $a$ and $b$, we write $a=O(b)$ if $a\leq\mathrm{{C}}\cdot b$;
and we write $a=\Omega(b)$ if $a\geq\mathrm{{C}}\cdot b$.

##### Overview.

In Section 2, we elaborate the problem setup of 1-bit compressed sensing. The
primary theoretical results and the comparison to the prior works are
developed in Section 3, and Section 4 presents useful extensions of our main
results. In Section 5 we provide empirical evidence to support our analysis.
Section 6 concludes the paper and all the proof details are deferred to the
Appendix (see the supplementary material).

##  2 Preliminaries

Let $\bar{\boldsymbol{x}}\in\mathbb{R}^{d}$ be the $s$-sparse signal of
interest. For now, we presume without loss of generality that it has unit
$\ell_{2}$-norm. While our concentration is on the 1-bit CS problem (1.2), we
begin our discussion with a more general observation model: for each
measurement $y_{i}\in\\{-1,1\\}$, instead of treating it as being generated
from a deterministic mapping through the sign function, we consider

$\mathbb{E}[y_{i}\mid\boldsymbol{a}_{i}]=\theta_{i}\left(\left\langle\boldsymbol{a}_{i},\bar{\boldsymbol{x}}\right\rangle\right),\
\forall\ i=1,\dots,n,$ (2.1)

where the mapping functions $\theta_{i}(\cdot)\in[-1,+1]$. Note that under the
observation model (1.2), $\theta_{i}(\cdot)$ is exactly the sign function. It
is worth mentioning that our model (2.1) is more general than the one
considered in prior works [25, 22, 26], since we allow different mapping
function for different sample, i.e. $\theta_{i}$ can be mutually distinct.

###  2.1 The Non-Convex Estimator

In order to recover $\bar{\boldsymbol{x}}$, we consider the estimate
$\hat{\boldsymbol{x}}$ that is a global optimum of the following program:

$\max_{\boldsymbol{x}\in\mathbb{R}^{d}}\
\boldsymbol{y}^{\top}\boldsymbol{A}\boldsymbol{x},\quad\operatorname{s.t.}\
\left\lVert\boldsymbol{x}\right\rVert_{0}\leq k,\
\left\lVert\boldsymbol{x}\right\rVert=1,$ (2.2)

where $\boldsymbol{y}=(y_{1},\dots,y_{n})^{\top}$ and
$\boldsymbol{A}=(\boldsymbol{a}_{1},\dots,\boldsymbol{a}_{n})^{\top}$. The two
constraints accommodate our prior knowledge on the signal
$\bar{\boldsymbol{x}}$, and the objective function seeks for a maximum
correlation between the input and output of $\theta_{i}(\cdot)$. We recall
that $\bar{\boldsymbol{x}}$ is $s$-sparse. The integer $k>0$ serves as the
only parameter in our estimator, and we need to tune it in practice. Ideally,
$k$ plays as an upper bound on the true sparsity $s$, which indicates that our
estimator is unbiased, i.e. the true signal is contained in the feasible set.
Once the condition is violated, we say the model is misspecified which needs a
particular treatment (see Section 4.3).

The optimal solution of the program (2.2) can be obtained by simple algebraic
calculation. Define the hard thresholding operator as follows:

$\mathcal{H}_{k}\left(\boldsymbol{z}\right):=\operatorname*{arg\,min}_{\boldsymbol{u}\in\mathbb{R}^{d},\left\lVert\boldsymbol{u}\right\rVert_{0}\leq
k}\left\lVert\boldsymbol{u}-\boldsymbol{z}\right\rVert.$ (2.3)

The following computational result is due to [5]. We present the proof in
Appendix A.1 for completeness.

######  Proposition 2.1.

The global optimum $\hat{\boldsymbol{x}}$ of the program (2.2) is given by

$\hat{\boldsymbol{x}}=\frac{\mathcal{H}_{k}\left(\boldsymbol{v}\right)}{\left\lVert\mathcal{H}_{k}\left(\boldsymbol{v}\right)\right\rVert},\
\text{where}\ \boldsymbol{v}:=\boldsymbol{A}^{\top}\boldsymbol{y}.$

Observe that the time complexity of calculating
$\boldsymbol{A}^{\top}\boldsymbol{y}$ is $O(dn)$, and applying the hard
thresholding costs $O(k\log d)$ since the $k$-sparse vector
$\mathcal{H}_{k}\left(\boldsymbol{z}\right)$ can be efficiently computed by
first sorting the elements of $\boldsymbol{z}$ in their magnitude, and then
retaining the top $k$ of them. Therefore, the total running time is $O(dn)$
given that $n$ is always greater than $k\log d$ in compressed sensing.

##  3 Main Results

We now move on to present the statistical estimation error under standard
conditions [25]. We assume that each observation $y_{i}$ depends on the
measurement vector $\boldsymbol{a}_{i}$ only through
$\left\langle\boldsymbol{a}_{i},\bar{\boldsymbol{x}}\right\rangle$. Namely,

  1. $(A1)$

given the inner product
$\left\langle\boldsymbol{a}_{i},\bar{\boldsymbol{x}}\right\rangle$, $y_{i}$
and $\boldsymbol{a}_{i}$ are conditionally independent.

We will focus on the standard Gaussian design of the sensing vectors. That is,

  1. $(A2)$

$\boldsymbol{a}_{i}\sim N\left(\boldsymbol{0},\boldsymbol{I}_{d\times
d}\right)$ for all $i=1,\dots,n$, and they are mutually independent.

The above sensing scheme offers a clean picture of theoretical understanding.
Furthermore, in the context of compressed sensing, we indeed have the control
of selecting the sensing vectors. Note that it is possible to relax the
assumption to correlated Gaussian design [25], or even non-Gaussian
measurements [2, 15].

In order to estimate the $s$-sparse signal $\bar{\boldsymbol{x}}$ from its
nonlinear measurements, we have to confine ourselves to a family of mapping
functions. As a matter of fact, if all functions $\theta_{i}$ output zero
almost surely, then no algorithm is able to recover the underlying signal.
Mathematically, the minimum requirement on the functions is that their input
and output are correlated. Let

$\lambda_{i}:=\mathbb{E}_{g\sim N(0,1)}\big{[}g\cdot\theta_{i}(g)\big{]},\
\forall\ i=1,\dots,n.$ (3.1)

In light of $(A1)$ and $(A2)$, $\lambda_{i}$ essentially characterizes the
correlation of interest [25]. While we do not impose individual condition on
$\lambda_{i}$, we need to assume

  1. $(A3)$

the average correlation $\lambda:=\frac{1}{n}\sum_{i=1}^{n}\lambda_{i}>0$.

Again, since we have the freedom to design $\theta_{i}(\cdot)$, we can always
replace all $\theta_{i}(\cdot)$ with $-\theta_{i}(\cdot)$ if we find
$\lambda<0$. We remark that a very recent work [33] studies the interesting
case $\lambda=0$ under extra assumptions.

We are now in the position to present performance guarantee of our estimate
$\hat{\boldsymbol{x}}$. We show that as soon as we collect $n=O(k\log d)$
measurements, it is possible to accurately approximate the direction of
$\bar{\boldsymbol{x}}$ with high probability from its non-linear measurements.

######  Theorem 3.1.

Assume $(A1)$, $(A2)$ and $(A3)$. Further assume
$\left\lVert\bar{\boldsymbol{x}}\right\rVert=1$,
$\left\lVert\bar{\boldsymbol{x}}\right\rVert_{0}=s$, and $k\geq s$. With
probability at least $1-d^{-10}$, we have

$\left\lVert\hat{\boldsymbol{x}}-{\bar{\boldsymbol{x}}}\right\rVert\leq\frac{\mathrm{{C}}}{\lambda}\sqrt{\frac{k\log
d}{n}}.$

######  Remark 3.2.

While our assumption on $\lambda$ is very mild, it is important to note that
in order to obtain near-optimal sample complexity, $\lambda$ must act as a
universal constant, which translates into an implicit requirement that most of
the $\lambda_{i}$’s are positive constants. Otherwise, Theorem 3.1 may offer
trivial guarantee. Consider, for example,
$\lambda_{1}=\lambda_{2}=\dots\lambda_{n-1}=0$ and $\lambda_{n}=1$. It
corresponds to $\lambda=1/n$ for which we have a trivial upper bound
$O(\sqrt{nk\log d})$ on the estimation error. This is not surprising since
many zero correlations indicate that the sampling power is wasted on the
associated samples (and thus recovery is impossible).

Fortunately, we can show that among many prevalent statistical models, the
parameter $\lambda$ acts as a universal non-zero constant, which indicates
that the sample complexity of our estimator is near-optimal in light of the
fact that the information-theoretic lower bound for infinite-bit CS is
$\Omega(k\log(d/k))$ [27].

###  3.1 Noiseless 1-Bit CS

Consider the problem (1.2) where
$\theta_{i}(g)=\operatorname{sign}\left(g\right)$. With some calculation,

$\lambda_{i}=\mathbb{E}_{g\sim
N(0,1)}[g\operatorname{sign}\left(g\right)]=\mathbb{E}[\left\lvert
g\right\rvert]=\sqrt{2/\pi}.$

Thus, we obtain the following corollary regarding the sample complexity of our
estimator.

######  Corollary 3.3.

Assume the same conditions as in Theorem 3.1. Under the model (1.2),

$\Pr\left(\left\lVert\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rVert\leq\epsilon\right)\geq
1-d^{-10}$

for any $\epsilon\in(0,1)$ provided that $n=O\left({\epsilon^{-2}}k\log
d\right)$.

###  3.2 Noisy 1-Bit CS

In real-world applications, the observations are not only highly quantized,
but are also grossly corrupted. In fact, owing to possible systematic errors
or human mistakes, the sign may be flipped with some probability. The noisy
model can thus be formulated as

$y_{i}=\xi_{i}\operatorname{sign}\left(\left\langle\boldsymbol{a}_{i},\bar{\boldsymbol{x}}\right\rangle\right),\quad\forall\
i=1,\ \dots,\ n,$ (3.2)

where $\xi_{i}$ is independent of $\boldsymbol{a}_{i}$ and

$\Pr(\xi_{i}=1)=1-p_{i},\quad\Pr(\xi_{i}=-1)=p_{i}$

for some $p_{i}\in[0,0.5)$. This gives a new mapping function and a new
correlation parameter as follows:

$\displaystyle\theta_{i}(g)=\operatorname{sign}\left(g\right)\cdot\mathbb{E}[\xi_{i}]=(1-2p_{i})\operatorname{sign}\left(g\right),$
$\displaystyle\lambda_{i}=\sqrt{2/\pi}(1-2p_{i}).$

######  Corollary 3.4.

Assume the same conditions as in Theorem 3.1. Under the model (3.2), for any
$\epsilon\in(0,1)$

$\Pr\left(\left\lVert\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rVert\leq\epsilon\right)\geq
1-d^{-10}$

provided that $n=O\left({\left((1-2p)\epsilon\right)^{-2}}k\log d\right)$
where $p=\frac{1}{n}\sum_{i=1}^{n}p_{i}$.

###  3.3 Proof Sketch of Theorem 3.1

Here we sketch the proof and highlight our novelty for the analysis. We defer
all technical details to Appendix A. Note that $\bar{\boldsymbol{x}}$ is a
feasible solution to (2.2). Owing to the optimality of $\hat{\boldsymbol{x}}$,
it holds that

$\boldsymbol{y}^{\top}\boldsymbol{A}\hat{\boldsymbol{x}}\geq\boldsymbol{y}^{\top}\boldsymbol{A}\bar{\boldsymbol{x}}.$

With some re-arrangement, we have

$\left\langle-\lambda\bar{\boldsymbol{x}},\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rangle\leq\left\langle\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\bar{\boldsymbol{x}},\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rangle.$

Since
$\left\lVert\bar{\boldsymbol{x}}\right\rVert=\left\lVert\hat{\boldsymbol{x}}\right\rVert=1$,
it follows that
$\left\langle-\lambda\bar{\boldsymbol{x}},\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rangle=\frac{\lambda}{2}\left\lVert\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rVert^{2}$.
Thus, we obtain

$\displaystyle\frac{\lambda}{2}\left\lVert\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rVert^{2}\leq$
$\displaystyle\
\left\langle\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\bar{\boldsymbol{x}},\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rangle$
$\displaystyle\leq$ $\displaystyle\
\left\lVert\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\bar{\boldsymbol{x}}\right\rVert_{\infty}\cdot\left\lVert\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rVert_{1}$
$\displaystyle\leq$ $\displaystyle\
\left\lVert\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\bar{\boldsymbol{x}}\right\rVert_{\infty}\cdot\sqrt{2k}\left\lVert\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rVert,$
(3.3)

where the second inequality follows from Hölder’s inequality. For the third
inequality, it follows from the facts that
$\left\lVert\boldsymbol{v}\right\rVert_{1}\leq\sqrt{\left\lVert\boldsymbol{v}\right\rVert_{0}}\cdot\left\lVert\boldsymbol{v}\right\rVert$
for all $\boldsymbol{v}\in\mathbb{R}^{d}$ and that
$\left\lVert\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rVert_{0}\leq 2k$.
Dividing both sides by
$\left\lVert\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rVert$ gives

$\left\lVert\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rVert\leq{\frac{\sqrt{2k}}{\lambda}\left\lVert\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\bar{\boldsymbol{x}}\right\rVert_{\infty}}.$
(3.4)

It remains to upper bound the infinity norm.

######  Lemma 3.5 ([47]).

Assume $(A1)$ and $(A2)$. Then for all $i=1,\dots,n$, it holds that
$\mathbb{E}[\boldsymbol{a}_{i}y_{i}]=\lambda_{i}\bar{\boldsymbol{x}}$.

In particular, Lemma 3.5 implies
$\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\bar{\boldsymbol{x}}=\frac{1}{n}\sum_{i=1}^{n}(\boldsymbol{a}_{i}y_{i}-\mathbb{E}[\boldsymbol{a}_{i}y_{i}])$.
Hence, we can apply Hoeffding’s inequality to show that the sum of independent
random variables concentrates around its mean with high probability. This is
formally stated below.

######  Lemma 3.6.

Consider the observation model (2.1). Assume $(A1)$, $(A2)$ and $(A3)$. With
probability at least $1-d^{-10}$ (over the random draw of $\boldsymbol{A}$) it
holds that

$\left\lVert\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\bar{\boldsymbol{x}}\right\rVert_{\infty}\leq\mathrm{{C}}\sqrt{\frac{\log
d}{n}}$

for some absolute constant $\mathrm{{C}}>0$.

Applying the inequality of the above lemma, we obtain Theorem 3.1. ∎

######  Remark 3.7 (Decomposition of Estimation Error).

As can be seen from the proof, if $\bar{\boldsymbol{x}}$ belongs to a generic
constraint set $\mathcal{K}$, then we can tailor our analysis as follows.
First, we will solve

$\max_{\boldsymbol{x}}\
\boldsymbol{y}^{\top}\boldsymbol{A}\boldsymbol{x},\quad\operatorname{s.t.}\
\boldsymbol{x}\in\mathcal{K}.$

We present the closed-form solution for certain $\mathcal{K}$ (a solution for
general $\mathcal{K}$ is hard to derive). Let
$\boldsymbol{v}=\boldsymbol{A}^{\top}\boldsymbol{y}$.

  * •

$\mathcal{K}=\\{\boldsymbol{x}\in\mathbb{R}^{d}:\left\lVert\boldsymbol{x}\right\rVert_{0}\leq
k,\left\lVert\boldsymbol{x}\right\rVert=1,\boldsymbol{x}\geq\boldsymbol{0}\\}$.
Let $S=\\{i:v_{i}>0\\}$ and $m=\left\lvert S\right\rvert$. If $m>k$, redefine
$S$ as the index set of the $k$ largest elements of $\boldsymbol{v}$. The
global optimum $\hat{\boldsymbol{x}}$ for such $\mathcal{K}$ is given as
follows: if $m=0$, then $\hat{\boldsymbol{x}}$ is the $i$th standard basis
vector where $i$ is the index of the largest entry of $\boldsymbol{v}$;
otherwise
$\hat{\boldsymbol{x}}=\boldsymbol{v}_{S}/\left\lVert\boldsymbol{v}_{S}\right\rVert$
where $\boldsymbol{v}_{S}$ is obtained by setting all elements of
$\boldsymbol{v}$ outside $S$ to zero.

  * •

$\mathcal{K}=\\{\boldsymbol{x}:\left\lVert\boldsymbol{x}\right\rVert_{0}\leq
k,\boldsymbol{x}\in\\{-1,0,1\\}^{d}\\}$. Let
$S=\operatorname{supp}\left(\boldsymbol{v},k\right)$. Then
$\hat{\boldsymbol{x}}=\operatorname{sign}\left(\boldsymbol{v}_{S}\right)$.

Now suppose that we are able to obtain a global optimum
$\bar{\boldsymbol{x}}$. Then following the same reasoning, (3.3) becomes

$\frac{\lambda}{2}\left\lVert\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rVert^{2}\leq\left\lVert\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\bar{\boldsymbol{x}}\right\rVert_{\infty}\cdot\rho_{\mathcal{K}}\left\lVert\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rVert,$
(3.5)

where

$\rho_{\mathcal{K}}:=\sup_{\boldsymbol{z}\in\mathcal{K}-\mathcal{K}}\
\frac{\left\lVert\boldsymbol{z}\right\rVert_{1}}{\left\lVert\boldsymbol{z}\right\rVert}$
(3.6)

is the restricted induced norm which is completely characterized by the signal
structure $\mathcal{K}$. While $\rho_{\mathcal{K}}\leq\sqrt{\left\lVert
z\right\rVert_{0}}$ for general $\mathcal{K}$, it is possible to show an
improved bound for specific $\mathcal{K}$. For instance, if $\mathcal{K}$ is
the set of $s$-sparse $\alpha$-strongly-decaying signals [14] for some
$\alpha\geq 2$, then $\rho_{\mathcal{K}}$ acts as an absolute constant, which
implies that the sample complexity in Theorem 3.1 can be improved to $O(\log
d)$. On the other hand, Lemma 3.6 tells us that the infinity norm in (3.5) is
oblivious of $\mathcal{K}$ (but depends on the distribution of
$\boldsymbol{A}$ and observation model). Therefore, if one is interested in a
sensing matrix $\boldsymbol{A}$ with heavy-tailed distributions, it suffices
to derive a new bound as what we did in Lemma 3.6.

###  3.4 Comparison to Prior Works

We first compare with two of the most important works on 1-bit CS [25, 26].
Both of them proposed to recover a signal with a generic structure
$\mathcal{K}$. Regarding theoretical guarantee, [25, Theorem 1.1] implies that
to obtain
$\left\lVert\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rVert\leq\epsilon$,
the sample size $n=O\left(\epsilon^{-4}k\log(d/k)\right)$ which is worse than
what we derived in Theorem 3.1 in terms of the dependence on $\epsilon$.
Though [26, Theorem 2.1] improved the sample complexity to
$n=O\left(\epsilon^{-2}k\log(d/k)\right)$, their proof is technically involved
(e.g. they applied high-dimensional geometric arguments) even specifying
$\mathcal{K}$ as the sparsity constraint. In contrast, we depart from their
theoretical analysis and reach the same guarantee with fundamental facts in
probability theory. Our analysis (Remark 3.7) shows the decomposition of
estimation error which is useful to develop new results for different sensing
schemes and signal structures.

In the seminal work of [21], a lower bound on the statistical error of sparse
approximation was established, and a non-convex program was proposed to
achieve the lower bound up to some logarithmic factor. Notably, their
guarantee is uniform, meaning that a single draw of the sensing vectors
ensures recovery of all sparse signals, whereas our result is specified to a
particular signal. Their sample complexity is $n=O(\epsilon^{-1}k\log d)$,
which has a better dependence on $\epsilon$ than this work. However, due to
the non-convex nature, it is not clear how to solve their program in
polynomial time. As a matter of fact, an iterative algorithm was devised with
compelling performance in practical problems, but it lacks theoretical backend
on the convergence behavior.

It is worth noting that [48, Theorem 4.3] claimed a sample complexity bound of
$O(s)$ for certain type of $\mathcal{K}$, which is a stronger result than what
we obtained in the paper. However, this may not be the true sample complexity
since in order to fulfill their conditions (i.e. $\bar{\boldsymbol{x}}_{\min}$
is sufficiently large), one needs $O(s\log d)$ samples. For the recovery of
general sparse signals, they showed a sample complexity bound similar to ours
through different non-convex estimators. In this case, our primary improvement
falls into the modular analysis and computational efficiency.

##  4 Extensions

Theorem 3.1 offers near-optimal guarantee on recovering the direction of the
signal $\bar{\boldsymbol{x}}$. In this section, we discuss when we can recover
its support set, and even its magnitude under extra conditions. In this
section, we focus on the elementary case that $\bar{\boldsymbol{x}}$ is
$s$-sparse.

###  4.1 Support Recovery

We first describe when our estimator reliably detects the support of
$\bar{\boldsymbol{x}}$. We would like point out that in some applications such
as medical diagnosis, it is of crucial importance to discover the determinants
of a disease (i.e. support recovery). Intuitively, a factor can be identified
only when it has “sufficient” impact on the disease. This notion of
significance is characterized by the following mathematical quantity:

$\bar{\boldsymbol{x}}_{\min}:=\min_{i\in\operatorname{supp}\left(\bar{\boldsymbol{x}}\right)}\left\lvert\bar{x}_{i}\right\rvert.$
(4.1)

Throughout the paper, we consider $\bar{\boldsymbol{x}}_{\min}\neq 0$, i.e.
the signal of interest is non-zero. We utilize a well-known fact to derive the
guarantee of support set of $\bar{\boldsymbol{x}}$.

######  Lemma 4.1.

For a given signal $\bar{\boldsymbol{x}}$, if

$\left\lVert\boldsymbol{x}-\bar{\boldsymbol{x}}\right\rVert<\bar{\boldsymbol{x}}_{\min},$

then it holds that
$\operatorname{supp}\left(\bar{\boldsymbol{x}}\right)\subset\operatorname{supp}\left(\boldsymbol{x}\right)$.

The lemma can be proved by algebra (see Appendix A.5), and has been widely
used in the literature [38]. In allusion to Theorem 3.1 (that is, let the
right-hand side therein be less than $\bar{\boldsymbol{x}}_{\min}$), we show
that the support set of $\bar{\boldsymbol{x}}$ is contained in that of our
estimate.

######  Theorem 4.2.

Assume the same conditions as in Theorem 3.1. Then
$\operatorname{supp}\left(\bar{\boldsymbol{x}}\right)\subset\operatorname{supp}\left(\hat{\boldsymbol{x}}\right)$
provided that

$\bar{\boldsymbol{x}}_{\min}>\frac{\mathrm{{C}}}{\lambda}\sqrt{\frac{k\log
d}{n}}.$

In particular, if we know exactly the sparsity of $\bar{\boldsymbol{x}}$, we
have
$\operatorname{supp}\left(\bar{\boldsymbol{x}}\right)=\operatorname{supp}\left(\hat{\boldsymbol{x}}\right)$.

######  Remark 4.3.

In the special case that $\bar{\boldsymbol{x}}$ is a binary vector, the above
theorem indicates exact signal recovery under near-optimal sample complexity.

######  Remark 4.4.

The proof of Lemma 4.1 essentially suggests that the minimum condition for
support recovery is
$\left\lVert\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rVert_{\infty}<\bar{\boldsymbol{x}}_{\min}$.
Yet we conjecture that even with such condition Theorem 4.2 may not be
significantly improved. Suppose that $N$ samples suffice for support recovery
of $\bar{\boldsymbol{x}}$. Consider a two-step scheme of sparse approximation:
1) recover support; 2) linear regression restricted on the obtained support
set. Since the second step needs $k$ samples, the total sample size is $N+k$.
As lower bound of sparse approximation is $k\log(d/k)$ we must have $N\geq
k\log(d/k)$.

###  4.2 Norm Estimation

In this section we consider $\left\lVert\bar{\boldsymbol{x}}\right\rVert\leq
R$ where $R$ is known, and we hope to estimate the norm of
$\bar{\boldsymbol{x}}$. In general, this is impossible in that the sign
function will absorb the magnitude information. Thus, we shall make a further
assumption for the data acquisition procedure:

$y_{i}=\operatorname{sign}\left(\left\langle\boldsymbol{a}_{i},\bar{\boldsymbol{x}}\right\rangle+b_{i}\right),\
\forall\ i=1,\dots,n,$ (4.2)

where $b_{i}$ are manually added noise which is known to us. The above
observation model is equivalent to

$y_{i}=\operatorname{sign}\left(\left\langle\boldsymbol{a}_{i}^{\prime},\bar{\boldsymbol{x}}^{\prime}\right\rangle\right),\
\forall\ i=1,\dots,n,$

where

$\boldsymbol{a}_{i}^{\prime}=\begin{pmatrix}\boldsymbol{a}_{i}\\\
b_{i}/R\end{pmatrix},\quad\bar{\boldsymbol{x}}^{\prime}=\frac{1}{\sqrt{\left\lVert\bar{\boldsymbol{x}}\right\rVert^{2}+R^{2}}}\begin{pmatrix}\bar{\boldsymbol{x}}\\\
R\end{pmatrix}.$

Note that the norm of $\bar{\boldsymbol{x}}$ has been encoded into
$\bar{\boldsymbol{x}}^{\prime}$ and $y_{i}$ bears the information of $b_{i}$,
which together paves the way for norm estimation. Also, all the
$\boldsymbol{a}_{i}^{\prime}$ are i.i.d. standard Gaussian random vectors
provided that

  1. $(A4)$

$b_{i}\sim N\left(0,R^{2}\right)$ for all $i=1,\dots,n$, they are mutually
independent, and are independent from all $\boldsymbol{a}_{i}$.

Since $\bar{\boldsymbol{x}}^{\prime}$ is an $(s+1)$-sparse signal, and has
unit $\ell_{2}$-norm, the estimation of $\bar{\boldsymbol{x}}^{\prime}$ from
(4.2) can be reduced to that of $\bar{\boldsymbol{x}}$ from (1.2) through the
following augmented program:

$\max_{{\boldsymbol{x}^{\prime}}\in\mathbb{R}^{d+1}}\
\boldsymbol{y}^{\top}{\boldsymbol{A}^{\prime}}{\boldsymbol{x}^{\prime}},\quad\operatorname{s.t.}\
\left\lVert{\boldsymbol{x}^{\prime}}\right\rVert_{0}\leq k,\
\left\lVert\boldsymbol{x}^{\prime}\right\rVert=1,$ (4.3)

where
$\boldsymbol{A}^{\prime}=(\boldsymbol{a}_{1}^{\prime},\dots,\boldsymbol{a}_{n}^{\prime})^{\top}$
and $k\geq s+1$. Proposition 2.1 immediately gives the global optimum of
(4.3):

$\hat{\boldsymbol{x}}^{\prime}=\mathcal{H}_{k}\left((\boldsymbol{A}^{\prime})^{\top}\boldsymbol{y}\right)/\left\lVert\mathcal{H}_{k}\left((\boldsymbol{A}^{\prime})^{\top}\boldsymbol{y}\right)\right\rVert.$
(4.4)

With the optimal solution, we are able to evaluate the magnitude of
$\bar{\boldsymbol{x}}$, as presented in the following theorem.

######  Theorem 4.5.

Consider the statistical model (4.2). Assume $(A1)$, $(A2)$, $(A3)$ and
$(A4)$. Further assume that $\left\lVert\bar{\boldsymbol{x}}\right\rVert\leq
R$, $\left\lVert\bar{\boldsymbol{x}}\right\rVert_{0}=s$, and $k\geq s+1$.
Write $\hat{\boldsymbol{x}}^{\prime}$ as

$\displaystyle\hat{\boldsymbol{x}}^{\prime}=\frac{(\boldsymbol{x}_{0};\
t_{0})}{\sqrt{\left\lVert\boldsymbol{x}_{0}\right\rVert^{2}+t_{0}^{2}}}.$

With probability at least $1-d^{-10}$ over the random draw of
$\boldsymbol{A}$, we either have

$\left\lVert\frac{R}{\left\lVert\boldsymbol{x}_{0}\right\rVert}\boldsymbol{x}_{0}-\bar{\boldsymbol{x}}\right\rVert\leq\frac{\mathrm{{C}}\cdot
R}{\lambda}\sqrt{\frac{k\log d}{n}}$

in the case $t_{0}=0$ (thus $\left\lVert\boldsymbol{x}_{0}\right\rVert\neq
0$); or have

$\left\lVert\frac{R}{t_{0}}\boldsymbol{x}_{0}-{\bar{\boldsymbol{x}}}\right\rVert\leq\frac{\mathrm{{C}}\cdot
R}{\lambda}\sqrt{\frac{k\log d}{n}}$

in the case $t_{0}\neq 0$.

######  Remark 4.6.

Interestingly, our theorem implies that when $t_{0}=0$ (i.e. the manually
added noise does not play a role in estimation),
$\frac{R}{\left\lVert\boldsymbol{x}_{0}\right\rVert}\boldsymbol{x}_{0}$ is a
good approximation to $\bar{\boldsymbol{x}}$. In other words, the norm of
$\bar{\boldsymbol{x}}$ is extremely close (or even equal) to $R$. This result
can be interpreted from another perspective: once we know the norm of
$\bar{\boldsymbol{x}}$ in advance, say
$\left\lVert\bar{\boldsymbol{x}}\right\rVert=R$, it is easy to see that
$\bar{\boldsymbol{x}}/R$ is feasible to program (2.2), and Theorem 3.1 already
implies

$\left\lVert\hat{\boldsymbol{x}}-\frac{\bar{\boldsymbol{x}}}{R}\right\rVert\leq\frac{\mathrm{{C}}}{\lambda}\sqrt{\frac{k\log
d}{n}},$

which is precisely the first inequality in Theorem 4.5 by noticing
$\boldsymbol{x}_{0}=\hat{\boldsymbol{x}}$ when $t_{0}=0$. Namely, there is no
need to consider model (4.2).

The analysis for $t_{0}\neq 0$ follows from Theorem 4 in [22], which showed
that as soon as we have a good approximation to the direction of
$\bar{\boldsymbol{x}}$, it is possible to estimate the magnitude if the
conditions in Theorem 4.5 are fulfilled. However, the scenario $t_{0}=0$ was
not addressed therein, and we make efforts to draw a formal analysis. See
Appendix A.6 for a full proof.

###  4.3 Model Misspecification

In our previous discussion, we always assume that the sparsity $k$ is equal
to, or greater than the true sparsity $s$, i.e. the true signal is contained
in the feasible set. However, sometimes we may choose $k<s$ in that we are not
aware of $s$. As a result, recovery of $\bar{\boldsymbol{x}}$ is impossible
but we can still hope to approximate its $k$ largest (i.e. most important)
components to a high precision.

We now elaborate the new results under the misspecified model. One notable
fact is that even when $k<s$, the normalized sparse vector
$\mathcal{H}_{k}\left(\bar{\boldsymbol{x}}\right)$ is feasible to the non-
convex program (2.2). Therefore, for sparse approximation we may apply the
same induction and obtain the following.

######  Theorem 4.7.

Assume the same conditions as in Theorem 3.1 but $k<s$. With probability at
least $1-d^{-10}$,

$\left\lVert\hat{\boldsymbol{x}}-\boldsymbol{z}\right\rVert\leq\frac{\mathrm{{C}}}{\lambda}\sqrt{\frac{k\log
d}{n}}+\sqrt{2k}\left\lVert\boldsymbol{z}-\bar{\boldsymbol{x}}\right\rVert_{\infty},$

where
$\boldsymbol{z}:=\frac{\mathcal{H}_{k}\left(\bar{\boldsymbol{x}}\right)}{\left\lVert\mathcal{H}_{k}\left(\bar{\boldsymbol{x}}\right)\right\rVert}$.

The proof can be found in Appendix A.4. The second term on the right-hand side
is the price we pay for model misspecification, and it vanishes as soon as
$k\geq s$. It is worth mentioning that it depends exclusively on the nature of
the signal $\bar{\boldsymbol{x}}$ rather than on the data acquisition
procedure. If the $s$-sparse signal $\bar{\boldsymbol{x}}$ has a light tail,
i.e. the first $k$ components dominate the magnitude, then
$\hat{\boldsymbol{x}}$ behaves as a good estimate. To see this, let us write
$\bar{\boldsymbol{x}}=(\bar{x}_{1},\dots,\bar{x}_{s},0,\dots,0)$ in descending
order (according to the magnitude of the elements). In this way
$\mathcal{H}_{k}\left(\bar{\boldsymbol{x}}\right)=(\bar{x}_{1},\dots,\bar{x}_{k},0,\dots,0)$.
Let us denote
$\alpha=\left\lVert\mathcal{H}_{k}\left(\bar{\boldsymbol{x}}\right)\right\rVert$
for now. It follows that

$\left\lVert\boldsymbol{z}-\bar{\boldsymbol{x}}\right\rVert_{\infty}=\max\bigg{\\{}\left(\frac{1}{\alpha}-1\right)\left\lvert\bar{x}_{1}\right\rvert,\
\left\lvert\bar{x}_{k+1}\right\rvert\bigg{\\}}.$ (4.5)

If the $k$ leading components dominate the remaining, then $\alpha\approx 1$
and $\left\lvert\bar{x}_{k+1}\right\rvert\approx 0$ hold simultaneously. As a
consequence,
$\left\lVert\boldsymbol{z}-\bar{\boldsymbol{x}}\right\rVert_{\infty}$ is close
to zero, under which Theorem 4.7 implies that we can accurately identify the
principal direction of $\bar{\boldsymbol{x}}$ given sufficient measurements.

Now we move on to discuss the support recovery of the top $k$ elements. In
light of Lemma 4.1, the support of $\hat{\boldsymbol{x}}$ is consistent with
that of $\mathcal{H}_{k}\left(\bar{\boldsymbol{x}}\right)$ as soon as the
sample size $n=O\left((\lambda\left\lvert\bar{x}_{k}\right\rvert)^{-2}k\log
d\right)$ and

$\sqrt{2k}\left\lVert\boldsymbol{z}-\bar{\boldsymbol{x}}\right\rVert_{\infty}<\left\lvert\bar{x}_{k}\right\rvert.$

Consider in (4.5) that the infinite norm is given by
$(1/\alpha-1)\left\lvert\bar{x}_{1}\right\rvert$. It follows that a sufficient
condition for support recovery is

$\left\lvert\bar{x}_{k+1}\right\rvert\leq\left(\frac{1}{\alpha}-1\right)\left\lvert\bar{x}_{1}\right\rvert<\frac{\left\lvert\bar{x}_{k}\right\rvert}{\sqrt{2k}}.$

The first inequality, which upper bounds
$\left\lvert\bar{x}_{k+1}\right\rvert$, indicates that for our purpose, the
elements outside of the support of interest cannot be too large. The second
inequality, which lower bounds $\left\lvert\bar{x}_{k}\right\rvert$, tells
that those inside of the support need to have sufficient magnitude.

Lastly, as we discussed in Section 4.2, a good approximation to the direction
of $\mathcal{H}_{k}\left(\bar{\boldsymbol{x}}\right)$ implies a good
estimation of the norm. We remark that this observation holds for a
misspecified model as well.

##  5 Experiments

This section is dedicated to examining the statistical error rate and
robustness of the our estimator. We focus on the noiseless model (1.2), and
will compare with the Lasso estimator [26] which showed state-of-the-art
performance.

##### Settings.

We implement our algorithm and the one of [26] in Matlab 2018, and perform all
the experiments on a single server which has two 3.2 GHz Intel Xeon
processors, each of which has 8 cores. The sensing vectors are chosen as
i.i.d. standard Gaussian. For the $s$-sparse signal $\bar{\boldsymbol{x}}$, we
first randomly choose the support set in a uniform manner, and draw each non-
zero element from an i.i.d. uniform distribution over the interval
$[-1000,1000]$. For each experiment to be presented, we generate 100 i.i.d.
copies of the true signal $\bar{\boldsymbol{x}}$ and report the averaged
performance. If not specified, we always set $k=s$.

##### Sparse Approximation.

We study how the estimation error
$\left\lVert\hat{\boldsymbol{x}}-\bar{\boldsymbol{x}}\right\rVert$ varies with
the sample size $n$. We fix the sparsity $s=20$, and consider the dimension
$d=2000$ and $d=10,000$. For each $d$, we increase $n$ from $10$ to $10,000$,
and for each configuration of $(d,n)$ we generate the sensing vectors as
aforementioned. The error curves are plotted in Figure 1. It shows that the
reconstruction error of our method decays much faster than [26], and it turns
out that their estimator incurs large error when the dimension is increased.
In contrast, our algorithm consistently produces accurate estimate.

Figure 1: Approximation error against sample size.

##### Support Recovery.

We use the same setting as in sparse approximation, but plot the cardinality
of the symmetric difference between
$\operatorname{supp}\left(\hat{\boldsymbol{x}}\right)$ and
$\operatorname{supp}\left(\bar{\boldsymbol{x}}\right)$. Since [26] may output
arbitrarily dense solution, for fair comparison we apply hard thresholding
with the true sparsity to their original estimate. Note that if their original
estimate already recovers the support, our post-processing does not hurt it.
In this way, the maximum error of both methods is $40$ (since $s=20$), and
zero error indicates perfect support recovery. Again, we observe in Figure 2
that our estimator outperforms the state-of-the-art.

Figure 2: Support recovery error against sample size.

##### Norm Estimation.

We use the estimate presented in Theorem 4.5 to approximate the signal
$\bar{\boldsymbol{x}}$ with $\left\lVert\bar{\boldsymbol{x}}\right\rVert\leq
R$. We choose $R=2\left\lVert\bar{\boldsymbol{x}}\right\rVert$, and illustrate
the absolute and relative errors in Figure 3. Note that we did not compare
with [26] because norm estimation was not addressed therein. The figure shows
that once we have sufficient samples, it is possible to accurately evaluate
the norm with the data collection scheme in Section 4.2.

Figure 3: Norm estimation error against sample size.

##### Model Misspecification.

In Figure 4 we record the estimation error (in logarithmic scale) of the
direction of $\mathcal{H}_{k}\left(\bar{\boldsymbol{x}}\right)$ when $k<s$. We
observe that even in this challenging scenario our estimate possesses a small
error. This matches our theoretical guarantee that our estimator is resilient
to model misspecification. It is noticeable that the curve of $k=1$ bumps more
often than others. The reason is that when $k=1$, the problem boils down to
hitting the unique non-zero position, and the estimation error per signal is
either $0$ or $2$ (which results in the bumping phenomenon).

Figure 4: Approximation error of the leading $k$ components of our method
under model misspecification. The true sparsity is $20$.

##  6 Conclusion

In this paper, we have studied an efficient estimator for recovering a sparse
signal from its binary measurements. On the computational side, the estimate
can be obtained by a one-step hard thresholding operator which enjoys economic
computational and memory cost. On the statistical side, we have shown that the
estimation error matches the information-theoretic lower bound up to some
logarithmic factor. We have also extended our results to support recovery and
norm estimation, and have proved near-optimal error rate in these scenarios.
For the estimation of all the three facets of a sparse signal, we have offered
rigorous theoretical evidence that our estimator is robust to model
misspecification. Finally, we have demonstrated through a comprehensive set of
experiments that the practical performance of our estimator matches perfectly
our analysis.

#### Acknowledgements

We thank Jing Wang and Chicheng Zhang for insightful discussions, and thank
the anonymous reviewers for helpful comments. This work is supported by the
startup funding from Stevens Institute of Technology.

##  Appendix A Omitted Proofs

This section provides a detailed proof for all the theoretical results.

###  A.1 Proof of Proposition 2.1

###### Proof.

Suppose that $\boldsymbol{x}$ is a feasible solution to (2.2). Let
$\mathcal{S}=\operatorname{supp}\left(\boldsymbol{x}\right)$. Consider the
objective function value

$\displaystyle\boldsymbol{y}^{\top}\boldsymbol{A}\boldsymbol{x}\leq\left\lVert\left(\boldsymbol{A}^{\top}\boldsymbol{y}\right)_{\mathcal{S}}\right\rVert\cdot\left\lVert\boldsymbol{x}\right\rVert=\left\lVert\left(\boldsymbol{A}^{\top}\boldsymbol{y}\right)_{\mathcal{S}}\right\rVert,$

where $\left(\boldsymbol{A}^{\top}\boldsymbol{y}\right)_{\mathcal{S}}$ is
interpreted as the $\left\lvert\mathcal{S}\right\rvert$-dimensional vector by
truncating the elements of $\boldsymbol{A}^{\top}\boldsymbol{y}$ outside the
index set $\mathcal{S}$. Evidently, the upper bound is maximized by the choice
$\mathcal{S}=\operatorname{supp}\left(\boldsymbol{A}^{\top}\boldsymbol{y},k\right)$,
and can be attained by picking $\boldsymbol{x}=\hat{\boldsymbol{x}}$ as given
in the proposition. ∎

###  A.2 Proof of Lemma 3.5

The proof follows closely from [47].

###### Proof.

As $\bar{\boldsymbol{x}}$ is treated as a fixed signal, we have

$\displaystyle\left\langle\bar{\boldsymbol{x}},\mathbb{E}[y_{i}\boldsymbol{a}_{i}]\right\rangle$
$\displaystyle=\mathbb{E}[y_{i}\left\langle\boldsymbol{a}_{i},\bar{\boldsymbol{x}}\right\rangle]$
$\displaystyle=\mathbb{E}\Big{[}\mathbb{E}\big{[}y_{i}\left\langle\boldsymbol{a}_{i},\bar{\boldsymbol{x}}\right\rangle\mid\boldsymbol{a}_{i}\big{]}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\left\langle\boldsymbol{a}_{i},\bar{\boldsymbol{x}}\right\rangle\mathbb{E}\big{[}y_{i}\mid\boldsymbol{a}_{i}\big{]}\Big{]}$
$\displaystyle=\mathbb{E}\big{[}\left\langle\boldsymbol{a}_{i},\bar{\boldsymbol{x}}\right\rangle\theta\left(\left\langle\boldsymbol{a}_{i},\bar{\boldsymbol{x}}\right\rangle\right)\big{]}$
$\displaystyle=\mathbb{E}_{g\sim
N(0,1)}\big{[}g\cdot\theta_{i}(g)\big{]}=\lambda_{i}.$ (A.1)

In the above expression, the second equality is by law of total expectation,
the third equality is by Assumption $(A1)$, the fourth equality is by Model
(2.1), and the last equality applies $(A2)$ and
$\left\lVert\bar{\boldsymbol{x}}\right\rVert=1$.

On the other side, by Gram-Schmidt process we can obtain an orthonormal basis
$\\{\bar{\boldsymbol{x}},\boldsymbol{v}_{1},\dots,\boldsymbol{v}_{d-1}\\}$.
For any $\boldsymbol{v}_{j}$, it follows that
$\left\langle\boldsymbol{a}_{i},\boldsymbol{v}_{j}\right\rangle$ is
independent from
$\left\langle\boldsymbol{a}_{i},\bar{\boldsymbol{x}}\right\rangle$, which
implies for all $1\leq j\leq d-1$

$\left\langle\boldsymbol{v}_{j},\mathbb{E}[y_{i}\boldsymbol{a}_{i}]\right\rangle=\mathbb{E}[y_{i}\left\langle\boldsymbol{a}_{i},\boldsymbol{v}_{j}\right\rangle]=\mathbb{E}[y_{i}]\cdot\mathbb{E}[\left\langle\boldsymbol{a}_{i},\boldsymbol{v}_{j}\right\rangle]=0.$
(A.2)

Now for the sake of contradiction suppose that
$\mathbb{E}[y_{i}\boldsymbol{a}_{i}]=\lambda_{i}\bar{\boldsymbol{x}}+\boldsymbol{u}$
with $\boldsymbol{u}\neq\boldsymbol{0}$. After plugging this expression of
$\mathbb{E}[y_{i}\boldsymbol{a}_{i}]$ into (A.2) and (A.2), we have that
$\boldsymbol{u}$ is orthogonal to the orthonormal basis, which implies that
$\boldsymbol{u}$ must be a zero vector. This yields a contradiction. ∎

###  A.3 Proof of Lemma 3.6

We use well-known concentration inequalities of Gaussian random variables to
prove the result.

###### Proof.

Recall that
$\boldsymbol{A}=(\boldsymbol{a}_{1},\dots,\boldsymbol{a}_{n})^{\top}$ and
$\boldsymbol{y}=(y_{1},\dots,y_{n})^{\top}$. Thus

$\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}=\frac{1}{n}\sum_{i=1}^{n}\boldsymbol{a}_{i}y_{i}.$

Consider the coordinate index $j\in\\{1,\dots,d\\}$. The $j$th coordinate of
$\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\bar{\boldsymbol{x}}$
is given by

$\left(\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\bar{\boldsymbol{x}}\right)^{(j)}=\frac{1}{n}\sum_{i=1}^{n}\Big{[}a_{i}^{(j)}y_{i}-\lambda_{i}\bar{x}^{(j)}\Big{]}$

where $a_{i}^{(j)}$ and $\bar{x}^{(j)}$ are the $j$th coordinate of
$\boldsymbol{a}_{i}$ and $\bar{\boldsymbol{x}}$ respectively. For a random
variable $v$, define the norm

$\lVert v\rVert_{\psi_{2}}:=\sup_{p\geq 1}p^{-1/2}\left(\mathbb{E}\left\lvert
v\right\rvert^{p}\right)^{1/p}.$

It is not hard to see that $\lVert a_{i}^{(j)}y_{i}\rVert_{\psi_{2}}=\lVert
a_{i}^{(j)}\rVert_{\psi_{2}}\leq\mathrm{{C}}_{0}$ where the inequality holds
since $a_{i}^{(j)}$ is standard normal [37]. Furthermore, for any random
variable $v$ we have

$\displaystyle\lVert v-\mathbb{E}v\rVert_{\psi_{2}}\leq\lVert
v\rVert_{\psi_{2}}+\lVert\mathbb{E}v\rVert_{\psi_{2}}=\lVert
v\rVert_{\psi_{2}}+\left\lvert\mathbb{E}v\right\rvert\leq\lVert
v\rVert_{\psi_{2}}+\mathbb{E}\left\lvert v\right\rvert\leq 2\lVert
v\rVert_{\psi_{2}}.$

Thus $\lVert a_{i}^{(j)}y_{i}-\lambda_{i}\bar{x}^{(j)}\rVert_{\psi_{2}}\leq
2\mathrm{{C}}_{0}$. Now by Proposition 5.10 in [37] we have

$\displaystyle\Pr\left(\left\lvert\frac{1}{n}\sum_{i=1}^{n}\Big{[}a_{i}^{(j)}y_{i}-\lambda_{i}\bar{x}^{(j)}\Big{]}\right\rvert\geq
t\right)\leq
e\cdot\exp\left(-\frac{\mathrm{{C}}_{1}t^{2}}{(2\mathrm{{C}}_{0})^{2}/n}\right).$

Picking $t=\mathrm{{C}}\sqrt{\frac{\log d}{n}}$ for some constant
$\mathrm{{C}}$ we have

$\displaystyle\Pr\left(\left\lvert\frac{1}{n}\sum_{i=1}^{n}\Big{[}a_{i}^{(j)}y_{i}-\lambda_{i}\bar{x}^{(j)}\Big{]}\right\rvert\geq\mathrm{{C}}\sqrt{\frac{\log
d}{n}}\right)\leq\exp\left(-11\log d\right)=d^{-11}.$

By union bound over the coordinates $j$, we show that

$\Pr\left(\left\lVert\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\bar{\boldsymbol{x}}\right\rVert_{\infty}\geq\mathrm{{C}}\sqrt{\frac{\log
d}{n}}\right)\leq d^{-10}$

which completes the proof. ∎

###  A.4 Proof of Theorem 3.1 and Theorem 4.7

The proof is very modular and thus facilitates the extension to other types of
signals and sensing matrices, as we discussed in Remark 3.7.

###### Proof.

Consider the program (2.2). Note that $\hat{\boldsymbol{x}}$ is optimal and
$\mathcal{H}_{k}\left(\bar{\boldsymbol{x}}\right)/\left\lVert\mathcal{H}_{k}\left(\bar{\boldsymbol{x}}\right)\right\rVert$
is feasible. It is worth mentioning that when $k\geq s$,
$\mathcal{H}_{k}\left(\bar{\boldsymbol{x}}\right)/\left\lVert\mathcal{H}_{k}\left(\bar{\boldsymbol{x}}\right)\right\rVert=\bar{\boldsymbol{x}}$.
For simplicity, we write
$\boldsymbol{z}={\mathcal{H}_{k}\left(\bar{\boldsymbol{x}}\right)}/{\left\lVert\mathcal{H}_{k}\left(\bar{\boldsymbol{x}}\right)\right\rVert}$.
It immediately follows that

$\boldsymbol{y}^{\top}\boldsymbol{A}\hat{\boldsymbol{x}}\geq\boldsymbol{y}^{\top}\boldsymbol{A}\boldsymbol{z}.$

With some re-arrangement, we have

$\left\langle-\lambda\boldsymbol{z},\hat{\boldsymbol{x}}-\boldsymbol{z}\right\rangle\leq\left\langle\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\boldsymbol{z},\hat{\boldsymbol{x}}-\boldsymbol{z}\right\rangle.$

Note that as
$\left\lVert\boldsymbol{z}\right\rVert=\left\lVert\hat{\boldsymbol{x}}\right\rVert=1$,
the left-hand side can be written as follows:

$\left\langle-\lambda\boldsymbol{z},\hat{\boldsymbol{x}}-\boldsymbol{z}\right\rangle=\frac{\lambda}{2}\left\lVert\hat{\boldsymbol{x}}-\boldsymbol{z}\right\rVert^{2}.$

Thus, we obtain

$\displaystyle\frac{\lambda}{2}\left\lVert\hat{\boldsymbol{x}}-\boldsymbol{z}\right\rVert^{2}\leq\left\langle\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\boldsymbol{z},\hat{\boldsymbol{x}}-\boldsymbol{z}\right\rangle$
$\displaystyle\leq\left\lVert\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\boldsymbol{z}\right\rVert_{\infty}\cdot\left\lVert\hat{\boldsymbol{x}}-\boldsymbol{z}\right\rVert_{1}$
$\displaystyle\leq\left\lVert\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\boldsymbol{z}\right\rVert_{\infty}\cdot\sqrt{2k}\left\lVert\hat{\boldsymbol{x}}-\boldsymbol{z}\right\rVert,$

where the second inequality follows from Hölder’s inequality, the third
inequality follows from the facts that
$\left\lVert\boldsymbol{v}\right\rVert_{1}\leq\sqrt{\left\lVert\boldsymbol{v}\right\rVert_{0}}\cdot\left\lVert\boldsymbol{v}\right\rVert$
for all $\boldsymbol{v}\in\mathbb{R}^{d}$ and that
$\left\lVert\hat{\boldsymbol{x}}-\boldsymbol{z}\right\rVert_{0}\leq 2k$.
Dividing both sides by
$\left\lVert\hat{\boldsymbol{x}}-\boldsymbol{z}\right\rVert$ gives

$\displaystyle\left\lVert\hat{\boldsymbol{x}}-\boldsymbol{z}\right\rVert\leq\frac{\sqrt{2k}}{\lambda}\left\lVert\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\boldsymbol{z}\right\rVert_{\infty}\leq{\frac{\sqrt{2k}}{\lambda}\left\lVert\frac{1}{n}\boldsymbol{A}^{\top}\boldsymbol{y}-\lambda\bar{\boldsymbol{x}}\right\rVert_{\infty}}+{\sqrt{2k}\left\lVert\boldsymbol{z}-\bar{\boldsymbol{x}}\right\rVert_{\infty}}.$

The first term on the right-hand side can be bounded from the above by Lemma
3.6. ∎

###  A.5 Proof of Lemma 4.1

This is a well recognized result, and we include the proof for completeness.

###### Proof.

For the sake of contradiction, suppose that
$\operatorname{supp}\left(\bar{\boldsymbol{x}}\right)$ is not contained in
$\operatorname{supp}\left(\boldsymbol{x}\right)$. That is, there exists an
index $j\in\\{1,\dots,d\\}$, such that $\bar{x}_{j}\neq 0,\quad x_{j}=0$.
Therefore, we have
$\left\lVert\boldsymbol{x}-\bar{\boldsymbol{x}}\right\rVert\geq\left\lvert\bar{x}_{j}\right\rvert\geq\bar{\boldsymbol{x}}_{\min}$,
which leads to a contradiction. ∎

###  A.6 Proof of Theorem 4.5

###### Proof.

Consider the program (4.3). Let the global optimum
$\hat{\boldsymbol{x}}^{\prime}=\frac{(\boldsymbol{x}_{0};\
t_{0})}{\sqrt{\left\lVert\boldsymbol{x}_{0}\right\rVert^{2}+t_{0}^{2}}}$ where
$\boldsymbol{x}_{0}\in\mathbb{R}^{d}$ and $t_{0}\in\mathbb{R}$. Since
$\bar{\boldsymbol{x}}^{\prime}$ is feasible, we may apply Theorem 3.1 and
obtain that with probability at least $1-d^{-10}$,

$\left\lVert\frac{(\bar{\boldsymbol{x}};\
R)}{\sqrt{\left\lVert\bar{\boldsymbol{x}}\right\rVert^{2}+R^{2}}}-\frac{(\boldsymbol{x}_{0};\
t_{0})}{\sqrt{\left\lVert\boldsymbol{x}_{0}\right\rVert^{2}+t_{0}^{2}}}\right\rVert\leq\frac{\mathrm{{C}}}{\lambda}\sqrt{\frac{k\log
d}{n}}=:{\delta}.$ (A.3)

For the case $t_{0}\neq 0$, the proof of Theorem 4 in [22] immediately implies
that

$\left\lVert\frac{R}{t_{0}}\boldsymbol{x}_{0}-\bar{\boldsymbol{x}}\right\rVert\leq\frac{\mathrm{{C}}_{1}\cdot
R}{\lambda}\sqrt{\frac{k\log d}{n}}.$

For the case $t_{0}=0$, it follows from (A.3)

$\left\lVert\frac{(\boldsymbol{x}_{1};\
1)}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}-{(\boldsymbol{x}_{2};\
0)}\right\rVert\leq\delta,$ (A.4)

where we write $\boldsymbol{x}_{1}=\bar{\boldsymbol{x}}/R$ and
$\boldsymbol{x}_{2}=\boldsymbol{x}_{0}/\left\lVert\boldsymbol{x}_{0}\right\rVert$.

On the other side, we have

$\displaystyle\left\lVert\boldsymbol{x}_{1}-\boldsymbol{x}_{2}\right\rVert$
$\displaystyle=\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}\left\lVert\frac{\boldsymbol{x}_{1}}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}-\frac{\boldsymbol{x}_{2}}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}\right\rVert$
$\displaystyle\stackrel{{\scriptstyle\zeta_{1}}}{{\leq}}\sqrt{2}\left\lVert\frac{\boldsymbol{x}_{1}}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}-\frac{\boldsymbol{x}_{2}}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}\right\rVert$
$\displaystyle\stackrel{{\scriptstyle\zeta_{2}}}{{\leq}}\sqrt{2}\left\lVert\frac{\boldsymbol{x}_{1}}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}-\boldsymbol{x}_{2}\right\rVert+\sqrt{2}\left\lVert\boldsymbol{x}_{2}-\frac{\boldsymbol{x}_{2}}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}\right\rVert$
$\displaystyle\stackrel{{\scriptstyle\zeta_{3}}}{{\leq}}\sqrt{2}\left\lVert\frac{\boldsymbol{x}_{1}}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}-\boldsymbol{x}_{2}\right\rVert+\sqrt{2}\left\lvert
1-\frac{1}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}\right\rvert$
$\displaystyle\stackrel{{\scriptstyle\zeta_{4}}}{{\leq}}\sqrt{2}\left\lVert\frac{\boldsymbol{x}_{1}}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}-\boldsymbol{x}_{2}\right\rVert+\sqrt{2}\left\lvert\frac{1}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}\right\rvert$
$\displaystyle\stackrel{{\scriptstyle\zeta_{5}}}{{\leq}}2\left(\left\lVert\frac{\boldsymbol{x}_{1}}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}-\boldsymbol{x}_{2}\right\rVert^{2}+\left\lvert\frac{1}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}\right\rvert^{2}\right)^{1/2}$
$\displaystyle=2\left\lVert\frac{(\boldsymbol{x}_{1};\
1)}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}-(\boldsymbol{x}_{2};\
0)\right\rVert$ $\displaystyle\leq 2\delta.$

In the above, the inequality $\zeta_{1}$ holds since
$\left\lVert\boldsymbol{x}_{1}\right\rVert\leq 1$, $\zeta_{2}$ follows from
the triangle inequality, $\zeta_{3}$ uses the fact
$\left\lVert\boldsymbol{x}_{2}\right\rVert\leq 1$. To see why $\zeta_{4}$
holds, note that $\left\lVert\boldsymbol{x}_{1}\right\rVert\leq 1$ implies

$\left\lvert
1-\frac{1}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}\right\rvert\leq
1-1/\sqrt{2}<1/\sqrt{2}\leq\frac{1}{\sqrt{\left\lVert\boldsymbol{x}_{1}\right\rVert^{2}+1}}.$

The last inequality $\zeta_{5}$ applies $a+b\leq\sqrt{2}\sqrt{a^{2}+b^{2}}$
for any two scalars $a$ and $b$. Therefore, we obtain that

$\left\lVert\frac{\bar{\boldsymbol{x}}}{R}-\frac{\boldsymbol{x}_{0}}{\left\lVert\boldsymbol{x}_{0}\right\rVert}\right\rVert\leq\frac{2\mathrm{{C}}}{\lambda}\sqrt{\frac{k\log
d}{n}},$

namely

$\left\lVert\frac{R}{\left\lVert\boldsymbol{x}_{0}\right\rVert}\boldsymbol{x}_{0}-\bar{\boldsymbol{x}}\right\rVert\leq\frac{2\mathrm{{C}}\cdot
R}{\lambda}\sqrt{\frac{k\log d}{n}}$

which completes the proof. ∎

## References

  * [1] Jayadev Acharya, Arnab Bhattacharyya, and Pritish Kamath.  Improved bounds for universal one-bit compressive sensing.  In Proceedings of the IEEE International Symposium on Information Theory, pages 2353–2357, 2017.
  * [2] Albert Ai, Alex Lapanowski, Yaniv Plan, and Roman Vershynin.  One-bit compressed sensing with non-Gaussian measurements.  Linear Algebra and its Applications, 441:222–239, 2014.
  * [3] Ery Arias-Castro, Emmanuel J. Candès, and Mark A. Davenport.  On the fundamental limits of adaptive sensing.  IEEE Transactions on Information Theory, 59(1):472–481, 2013\.
  * [4] Pranjal Awasthi, Maria-Florina Balcan, and Philip M. Long.  The power of localization for efficiently learning linear separators with noise.  Journal of the ACM, 63(6):50:1–50:27, 2017.
  * [5] Sohail Bahmani, Petros T. Boufounos, and Bhiksha Raj.  Robust 1-bit compressive sensing via gradient support pursuit.  CoRR, abs/1304.6627, 2013.
  * [6] Richard G. Baraniuk, Simon Foucart, Deanna Needell, Yaniv Plan, and Mary Wootters.  Exponential decay of reconstruction error from binary measurements of sparse signals.  IEEE Transactions on Information Theory, 63(6):3368–3385, 2017\.
  * [7] Sonia A. Bhaskar.  Probabilistic low-rank matrix completion from quantized measurements.  Journal of Machine Learning Research, 17(60):1–34, 2016.
  * [8] Thomas Blumensath and Mike E. Davies.  Iterative hard thresholding for compressed sensing.  Applied and Computational Harmonic Analysis, 27(3):265–274, 2009\.
  * [9] Petros Boufounos and Richard G. Baraniuk.  1-bit compressive sensing.  In Proceedings of the 42nd Annual Conference on Information Sciences and Systems, pages 16–21, 2008.
  * [10] Tony T. Cai, Weidong Liu, and Xi Luo.  A constrained $\ell_{1}$ minimization approach to sparse precision matrix estimation.  Journal of the American Statistical Association, 106(494):594–607, 2011.
  * [11] Emmanuel J. Candès and Terence Tao.  Decoding by linear programming.  IEEE Transactions on Information Theory, 51(12):4203–4215, 2005\.
  * [12] Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders.  Atomic decomposition by basis pursuit.  SIAM Journal on Scientific Computing, 20(1):33–61, 1998.
  * [13] Mark A. Davenport, Yaniv Plan, Ewout van den Berg, and Mary Wootters.  1-bit matrix completion.  Information and Inference: A Journal of the IMA, 3(3):189–223, 2014.
  * [14] Mark A. Davenport and Michael B. Wakin.  Analysis of orthogonal matching pursuit using the restricted isometry property.  IEEE Transactions on Information Theory, 56(9):4395–4401, 2010\.
  * [15] Sjoerd Dirksen and Shahar Mendelson.  Non-gaussian hyperplane tessellations and robust one-bit compressed sensing.  CoRR, abs/1805.09409, 2018.
  * [16] David L. Donoho.  Compressed sensing.  IEEE Transactions on Information Theory, 52(4):1289–1306, 2006\.
  * [17] Jianqing Fan and Yingying Fan.  High dimensional classification using features annealed independence rules.  Annals of Statistics, 36(6):2605–2637, 2008.
  * [18] Jianqing Fan and Runze Li.  Variable selection via nonconcave penalized likelihood and its oracle properties.  Journal of the American Statistical Association, 96(456):1348–1360, 2001.
  * [19] Sivakant Gopi, Praneeth Netrapalli, Prateek Jain, and Aditya V. Nori.  One-bit compressed sensing: Provable support and vector recovery.  In Proceedings of the 30th International Conference on Machine Learning, pages 154–162, 2013.
  * [20] Xiaolin Huang and Ming Yan.  Nonconvex penalties with analytical solutions for one-bit compressive sensing.  Signal Processing, 144:341–351, 2018.
  * [21] Laurent Jacques, Jason N. Laska, Petros T. Boufounos, and Richard G. Baraniuk.  Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors.  IEEE Transactions on Information Theory, 59(4):2082–2102, 2013\.
  * [22] Karin Knudson, Rayan Saab, and Rachel Ward.  One-bit compressive sensing with norm estimation.  IEEE Transactions on Information Theory, 62(5):2748–2758, 2016\.
  * [23] Zongming Ma.  Sparse principal component analysis and iterative thresholding.  The Annals of Statistics, 41(2):772–801, 2013.
  * [24] Yurii Nesterov.  Introductory Lectures on Convex Optimization: A Basic Course, volume 87 of Applied Optimization.  Springer US, 2004.
  * [25] Yaniv Plan and Roman Vershynin.  Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach.  IEEE Transactions on Information Theory, 59(1):482–494, 2013\.
  * [26] Yaniv Plan, Roman Vershynin, and Elena Yudovina.  High-dimensional estimation with geometric constraints.  Information and Inference: A Journal of the IMA, 6(1):1–40, 2017.
  * [27] Garvesh Raskutti, Martin J. Wainwright, and Bin Yu.  Minimax rates of estimation for high-dimensional linear regression over $\ell_{q}$-balls.  IEEE Transactions on Information Theory, 57(10):6976–6994, 2011\.
  * [28] Jie Shen, Pranjal Awasthi, and Ping Li.  Robust matrix completion from quantized observations.  In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 397–407, 2019.
  * [29] Jie Shen and Ping Li.  On the iteration complexity of support recovery via hard thresholding pursuit.  In Proceedings of the 34th International Conference on Machine Learning, pages 3115–3124, 2017.
  * [30] Jie Shen and Ping Li.  Partial hard thresholding: Towards a principled analysis of support recovery.  In Proceedings of the 31st Annual Conference on Neural Information Processing Systems, pages 3127–3137, 2017.
  * [31] Jie Shen and Ping Li.  A tight bound of hard thresholding.  Journal of Machine Learning Research, 18(208):1–42, 2018.
  * [32] Jie Shen and Chicheng Zhang.  Attribute-efficient learning of halfspaces with malicious noise: Near-optimal label complexity and noise tolerance.  CoRR, abs/2006.03781, 2020.
  * [33] Christos Thrampoulidis and Ankit Singh Rawat.  Lifting high-dimensional non-linear models with gaussian regressors.  In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 3206–3215, 2019.
  * [34] Robert Tibshirani.  Regression shrinkage and selection via the Lasso.  Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 1996.
  * [35] Joel A. Tropp and Anna C. Gilbert.  Signal recovery from random measurements via orthogonal matching pursuit.  IEEE Transactions on Information Theory, 53(12):4655–4666, 2007\.
  * [36] Leslie G. Valiant.  A theory of the learnable.  Communications of the ACM, 27(11):1134–1142, 1984.
  * [37] Roman Vershynin.  Introduction to the non-asymptotic analysis of random matrices.  CoRR, abs/1011.3027, 2010.
  * [38] Martin J. Wainwright.  Sharp thresholds for high-dimensional and noisy sparsity recovery using $\ell_{1}$-constrained quadratic programming (Lasso).  IEEE Transactions on Information Theory, 55(5):2183–2202, 2009\.
  * [39] Jing Wang, Jie Shen, and Ping Li.  Provable variable selection for streaming features.  In Proceedings of the 35th International Conference on Machine Learning, pages 5158–5166, 2018.
  * [40] Jing Wang, Jie Shen, Ping Li, and Huan Xu.  Online matrix completion for signed link prediction.  In Proceedings of the 10th ACM International Conference on Web Search and Data Mining, pages 475–484, 2017.
  * [41] Songbai Yan and Chicheng Zhang.  Revisiting Perceptron: Efficient and label-optimal learning of halfspaces.  In Proceedings of the 31st Annual Conference on Neural Information Processing Systems, pages 1056–1066, 2017.
  * [42] Xiao-Tong Yuan, Ping Li, and Tong Zhang.  Exact recovery of hard thresholding pursuit.  In Proceedings of the 30th Annual Conference on Neural Information Processing Systems, pages 3558–3566, 2016.
  * [43] Xiao-Tong Yuan and Tong Zhang.  Truncated power method for sparse eigenvalue problems.  Journal of Machine Learning Research, 14(1):899–925, 2013.
  * [44] Chicheng Zhang.  Efficient active learning of sparse halfspaces.  In Proceedings of the 31st Annual Conference On Learning Theory, pages 1856–1880, 2018.
  * [45] Chicheng Zhang, Jie Shen, and Pranjal Awasthi.  Efficient active learning of sparse halfspaces with arbitrary bounded noise.  CoRR, abs/2002.04840, 2020.
  * [46] Cun-Hui Zhang.  Nearly unbiased variable selection under minimax concave penalty.  The Annals of statistics, pages 894–942, 2010.
  * [47] Lijun Zhang, Jinfeng Yi, and Rong Jin.  Efficient algorithms for robust one-bit compressive sensing.  In Proceedings of the 31st International Conference on Machine Learning, pages 820–828, 2014.
  * [48] Rongda Zhu and Quanquan Gu.  Towards a lower sample complexity for robust one-bit compressed sensing.  In Proceedings of the 32nd International Conference on Machine Learning, pages 739–747, 2015.