From Lemma <ref> which is presented at the end of this subsection, $\|h_{LN}'\|_\infty \leq 1$ and $\|h_{LN}''\|_\infty \leq 2$.  Also $A''(t) = e^t  / (1+e^t )^2$ is bounded by $1/4$ and $|A'(h_{LN}(t))-z|\leq 1 $ for any $t$ and $z \in \{0,1\}$, since  $0 \leq A'(h_{LN}(t)) \leq 1, \forall t$. Thus

\begin{align*}
|\ell'(t,z) | \leq 1, \quad |\rho_I(t)| \leq \frac{1}{4}, \quad\mbox{and} \quad |\rho_R(t,z)| \leq \|h_{LN}''\|_\infty \leq 2,\quad \forall z \in \{0,1\}, \forall t,
\end{align*}

and $\max\{\|\ell'\|_\infty, \|\rho_I\|_\infty, \|\rho_R\|_\infty \}$ is bounded by $2$.

To verify that $\ell''$ is $L_\ell$-Lipschitz where $L_\ell$ does not depend on $t$, it is sufficient to show that the gradients of $\rho_I$ and $\rho_R$ are bounded independent of $t$. By calculation, we have

\begin{align*}
\rho_I'(t) &= A'''(h_{LN}(t))h_{LN}'(t)^3 + 2A''(h_{LN}(t))h_{LN}'(t)^2h_{LN}''(t)\\
\rho_R'(t,z) &= A''(h_{LN}(t))h_{LN}'(t)h_{LN}''(t)+\{A'(h_{LN}(t))-z\} h_{LN}'''(t).
\end{align*}

We bound each term separately. As other terms can be bounded similarly other than the term involving $A'''$, it is sufficient to show that $A'''(t)$ is bounded by an absolute constant. We have,

\begin{align*}
|A'''(t)| &= \left\lvert\frac{e^t }{(1+e^t )^2 }- \frac{2e^{2t}}{(1+e^t )^3}\right\rvert \leq  \left\lvert\frac{e^t }{(1+e^t )^2 }\right\rvert+ \left\lvert \left(\frac{2e^{t}}{(1+e^t )^2}\right)\left(\frac{e^{t}}{1+e^t } \right)\right\rvert \leq \frac{1}{4} + \frac{1}{2} \leq 1.
\end{align*}

Finally, we present the Lemma about the boundedness of $h_{LN}',h_{LN}''$ and $h_{LN}'''$.

There exists $C \leq 7$ such that $\max \{ \|h_{LN}'\|_\infty,\|h_{LN}''\|_\infty,\|h_{LN}'''\|_\infty\} \leq C$ for $h_{LN} = (A')^{-1}\circ g_{LN}^{-1}$.

From the definition of $g_{LN}$ and $h_{LN}$ in (<ref>), we have

\begin{align*}
h_{LN}(t) := \log \left(\frac{(1-\rho_1-\rho_0)\mu(t) +\rho_0}{1-(1-\rho_1-\rho_0)\mu(t) -\rho_0}\right).
\end{align*}

$ a= 1-\rho_1-\rho_0$ and $b = \rho_0$.
We have $a \mu(t) + b \leq a+b <1$ and $a \mu(t) \leq a\mu(t)+b$ for any $t$. Then $\forall t$,

\begin{align}
&\frac{a\mu(t)}{a\mu(t)+b} \leq 1 \quad \mbox{and} \quad \frac{a(1-\mu(t))}{1-a\mu(t)-b} <1 \label{eq:p_ineq}
\end{align}

By definition of $h_{LN}(t)= \log (a \mu(t) + b) - \log (1-a \mu(t)-b)$,

\begin{align*}
h_{LN}'(t) &= \frac{d}{d\mu(t)} \log \left(\frac{a \mu(t) + b}{1-(a \mu(t) + b)}\right) \frac{d\mu(t)}{dt}\\
&= \frac{a \mu(t) (1-\mu(t)) }{ (a \mu(t)+b) (1-a\mu(t)-b)} \leq 1
\end{align*}

by the fact that
$$ \frac{d\mu(t)}{dt} = A''(t) = \mu(t)(1-\mu(t))$$
and the inequalities (<ref>). In particular, $h_{LN}' \geq 0$ and $\|h_{LN}'\|_\infty \leq 1$.

Now we bound $h_{LN}''$. From elementary calculation, it can be shown that

\begin{align*}
h_{LN}''(t) &= h_{LN}'(t) (1- 2\mu(t)) -h_{LN}'(t)^2(1-2(a\mu(t)+b)),\\
h_{LN}'''(t) &=  h_{LN}''(t) \left\lbrace 1- 2\mu(t) -2h_{LN}'(t)(1-2(a\mu(t)+b))\right\rbrace\\
&\quad -2\mu(t) (1-\mu(t)) h_{LN}'(t)(1-ah_{LN}'(t)).
\end{align*}

In particular,

\begin{align*}
|h_{LN}''(t)| \leq h_{LN}'(t) |1- 2\mu(t)| +h_{LN}'(t)^2|1-2(a\mu(t)+b)| \leq 2 \|h_{LN}'\|_\infty  \leq 2
\end{align*}

since $\max_{0\leq \mu \leq 1} |1-2\mu| = 1$ and $0\leq \mu(t),a \mu(t) +b \leq 1$, for all $t$. Also,

\begin{align*}
|h_{LN}'''(t)| &\leq |h_{LN}''(t)| \left\lbrace |1- 2\mu(t)| + 2h_{LN}'(t)|1-2(a\mu(t)+b)|\right\rbrace \\
&\qquad +2\mu(t) (1-\mu(t)) h_{LN}'(t)(1-ah_{LN}'(t))\\
& \leq  3 \|h_{LN}''\|_\infty + \frac{1}{2}.
\end{align*}

§ PROOFS FOR RESULTS IN SECTION <REF>

§.§ Proof of Proposition <ref>

First, we note that the inequality (<ref>) holds trivially for $\beta=\beta_0$. For any $\beta\in \B_2(r) \setminus \{\beta_0\}$ and $\Delta_0 := \beta- \beta_0$,

\begin{align*}
&\langle \triangledown \L_n^\ell(\beta) - \triangledown \L_n^\ell(\beta_0),\Delta_0\rangle  \\
&= \langle  \triangledown \L^\ell(\beta)-\triangledown \L^\ell(\beta_0), \Delta_0\rangle+ \langle \triangledown \L_n^\ell(\beta) - \triangledown \L^\ell(\beta), \Delta_0\rangle + \langle \triangledown \L^\ell(\beta_0) - \triangledown \L_n^\ell(\beta_0), \Delta_0\rangle\\
&\geq \langle \triangledown \L^\ell(\beta), \Delta_0\rangle - \left( \left\lvert \frac{ \langle \triangledown \L_n^\ell(\beta) - \triangledown \L^\ell(\beta), \Delta_0\rangle}{\|\Delta_0\|_1}\right\rvert+\|  \triangledown \L_n^\ell(\beta_0)\|_\infty \right) \|\Delta_0\|_1
\end{align*}

using $\triangledown \L^\ell(\beta_0)=0$ and Hölder's inequality. From (<ref>), we have

\begin{align*}\langle  \triangledown \L^{\ell}(\beta),\Delta_0 \rangle
\geq \alpha_\ell \|\Delta_0\|_2^2,
\end{align*}

where $\alpha_\ell:= C_r C_\lambda/2$, for $C_r$ defined in (<ref>). Let

\begin{align}
\mathcal{E} := \left \lbrace \left\lvert \frac{ \langle \triangledown \L_n^\ell(\beta) - \triangledown \L^\ell(\beta), \Delta_0\rangle}{\|\Delta_0\|_1}\right\rvert+\|  \triangledown \L_n^\ell(\beta_0)\|_\infty  \leq \tau_\ell \sqrt{\frac{\log p}{n}}, \forall \beta \in \B_2(r) \setminus \{\beta_0\} \right\rbrace,
\end{align}

for $\tau_\ell := c\cdot ( C_\ell K_X + C_1(T_\star+ L_\star \tau))$, where $c>0$ is an absolute constant, and $T_\star, L_\star$, $\tau$, and $C_1$ are constants which are defined in Lemma <ref>. On $\mathcal{E}$, we note that

\begin{align*}
\langle \triangledown \L_n^\ell(\beta) - \triangledown \L_n^\ell(\beta_0),\beta - \beta_0\rangle \geq \alpha_\ell \|\beta - \beta_0\|_2^2 - \tau_\ell \sqrt{\frac{\log p}{n}}\|\beta - \beta_0\|_1.
\end{align*}

Therefore, it is sufficient to show that $\P(\mathcal{E}) \geq 1-\epsilon$.

First, we show $\|\triangledown \L_n^\ell(\beta_0) \|_\infty \leq c_0 C_\ell K_X\sqrt{\frac{\log p}{n}}$ w.p $1-\epsilon/2$, where $c_0$ is an absolute constant. Note,

\begin{align*}
\|\triangledown \L_n^\ell(\beta_0) \|_\infty = \max_{1\leq j\leq p} \left\lvert \frac{1}{n} \sum_{i=1}^n \ell'(\x_i^\top \beta_0,\z_i)\x_{ij}  \right\rvert.
\end{align*}

We use the following Lemma <ref> to bound $\|\triangledown \L_n^\ell(\beta_0) \|_\infty$.

Suppose $(\xi_{ij})_{1\leq i\leq n,1\leq j \leq p}$ are random variables such that $\xi_{ij}$ is a mean-zero sub-gaussian with parameter $C_\xi$ and $(\xi_{ij})_{i=1}^n$ are independent for any $j \in \{1,\dots,p\}$. Then,

\[\P\left(\max_{1\leq j\leq p} \left\lvert \frac{1}{n} \sum_{i=1}^n \xi_{ij}  \right\rvert \geq  3C_\xi \sqrt{\frac{\log p}{n}} \right)\leq \frac{1}{p^7}. \]

$ \frac{1}{n} \sum_{i=1}^n \xi_{ij}$ is sub-gaussian with parameter $C_\xi/\sqrt{n}$. By taking a union bound, for any $t\geq 0 $ we have

\begin{align*}
\P\left(  \max_{1\leq j\leq p} \left\lvert \frac{1}{n} \sum_{i=1}^n \xi_{ij}  \right\rvert \geq t \sqrt{\frac{\log p}{n}}\right) \leq  \exp (- t^2 \log p/C_\xi^2 + \log 2p)
\end{align*}

Take $t^2 = 9C_\xi^2$. Then $\|\triangledown \L_n(\beta_0) \|_\infty \leq t\sqrt{\frac{\log p}{n}}$ with probability at least $1-1/p^7$.

Taking $\xi_{ij} = \ell'(\x_i^\top \beta_0,\z_i)\x_{ij}$ in Lemma <ref>, we have, $\E[|\xi_{ij}|^{k}]^{1/k} \leq C_\ell \E[|\x_{ij}|^k]^{1/k} \leq  \sqrt{k} C_\ell K_X$ for any $k\geq 1$ by Assumption A<ref>' and A<ref>. Also, $\E[\xi_{ij}] = 0$ since $\E[\z_i|\x_i] = A'(h(\x_i^\top \beta_0))$. Therefore, $\xi_{ij}$ is a mean-zero sub-gaussian variable with parameter $c_0 C_\ell K_X$, where $c_0$ is an absolute constant. Then from Lemma <ref>, $\|\triangledown \L_n(\beta_0) \|_\infty \leq c_0 C_\ell K_X\sqrt{\frac{\log p}{n}}$ with probability at least $1-1/p^7$. Thus, for $n \geq C \cdot (2/\epsilon)^{1/7}$ for a sufficiently large constant $C$, we have $\|\triangledown \L_n(\beta_0) \|_\infty \leq c_0 C_\ell K_X\sqrt{\frac{\log p}{n}}$ w.p. at least $1-\epsilon/2$, in the regime of interest $p \gg n$.

The bound for the second term can be obtained by taking advantage of the uniform convergence result of the directional derivative of the loss function in Mei et al., 2018, and we summarize the result for the case of $\L_n(\beta)$ in Lemma <ref>. Taking $\delta =\epsilon/2$ in Lemma <ref>, we obtain $\P(\mathcal{E}) \geq 1-\epsilon$, as desired.

There exists a constant $C_1>0$, which depends on model parameters $(r,K_X,C_\ell,L_\ell)$ and $\delta$ such that

\begin{align}
\P\left( \sup_{\beta \in \B_2(r)\setminus \{\beta_0\}} \left\lvert \frac{ \langle \triangledown \L_n^\ell(\beta) - \triangledown \L^\ell(\beta), \beta-\beta_0\rangle}{\|\beta-\beta_0\|_1}\right\rvert \leq C_1(T_\star + L_\star \tau) \sqrt{\frac{ \log (np)}{n}}\right) \geq 1-\delta,
\end{align}

where $\tau = K_X \max\{C_\ell, L_\ell^{1/3} \}$, $T_\star = C_\ell C_X$, and $L_\star = C_\rho + C_\ell (C_bC_d+1)$.

We verify Assumptions 2-5 in Mei et al., 2018. From the proof of Lemma <ref>, we have already checked that Assumption 2 and 3 in Mei et al., 2018 are satisfied under A<ref>' and A<ref>. We thus check Assumptions 4 and 5 in Mei et al., 2018, which verify the existence of $T_\star$ and $L_\star$, where $T_\star$ is a constant such that $\|\ell'(\x^\top \beta, \z)\x\|_\infty \leq T_\star$ a.s., and $L_\star$ is a Lipschitz constant for the function $g(\cdot,\cdot) \rightarrow \mathbb{R}$, which is defined as follows:

\begin{align*}
g(\x^\top (\beta-\beta_0), (\x,\z))=\langle \ell'(\x^\top \beta, \z)\x, \beta-\beta_0\rangle.
\end{align*}

For the existence of $T_\star$,
$\|\ell'(\x^\top \beta, \z)\x\|_\infty \leq C_\ell C_X$, by Assumption A<ref>' and A<ref>. Thus we can let $T_\star = C_\ell C_X$. For Assumption 5 in Mei et al., 2018,

\begin{align*}
\langle \ell'(\x^\top \beta, \z)\x , \beta-\beta_0\rangle &= (A'(h(\x^\top \beta))-\z)h'(\x^\top \beta)\x^\top (\beta-\beta_0)\\
&=g(\x^\top (\beta-\beta_0); (\x,\z))
\end{align*}

for $g(t;(\x,\z)) := \ell'(t+\x^\top \beta_0,\z)t$. We show that $g(t;(\x,\z))$ is Lipschitz with respect to $t$ under Assumption A<ref>. Taking a derivative with respect to $t$,

\begin{align*}
g'(t;(\x,\z)) = \ell''(t+\x^\top \beta_0,\z)t+\ell'(t+\x^\top \beta_0,\z).
\end{align*}

\begin{align*}
|g'(t;(\x,\z))| &\leq |\ell''(t+\x^\top \beta_0,\z)(t+\x^\top \beta_0)|+|\ell''(t+\x^\top \beta_0,\z)\x^\top \beta_0|+ |\ell'(t+\x^\top \beta_0,\z)|\\
&\leq C_\rho + C_\ell (C_bC_d+1)
\end{align*}

by Assumptions A<ref>' and A<ref>, noting $|\x^\top \beta_0|\leq C_bC_d$ a.s. by Assumption A<ref>. Therefore $L_\star$ can be taken as $L_\star = C_\rho + C_\ell (C_bC_d+1)$.

§.§ Proof of Proposition <ref>

\begin{align*}
\langle \triangledown \L_n^{s}(\beta) - \triangledown \L_n^{s} (\beta_0) ,\beta - \beta_0 \rangle
&= \frac{1}{n}\sum_{i=1}^n  (\mu(\x_i^\top \beta) -\mu(\x_i^\top \beta_0))\x_i^\top (\beta-\beta_0)\\
&= \frac{1}{n}\sum_{i=1}^n  \mu'(\x_i^\top \beta_0 + v \x_i^\top  (\beta-\beta_0 ))(\x_i^\top (\beta-\beta_0))^2
\end{align*}

Then from the proof of Proposition 2 in Negahban et al., 2012, there exist positive constants $\kappa_1$ and $\kappa_2$ such that

\begin{align*}
\langle \triangledown \L_n^{s} (\beta) - \triangledown \L_n^{s} (\beta_0) ,\beta - \beta_0 \rangle
\geq \kappa_1 \|\Delta\|_2 \left(\|\Delta\|_2 - \kappa_2 \sqrt{\frac{\log p}{n}}\|\Delta\|_1 \right),\quad \forall \beta \in \B_2(1;\beta_0)
\end{align*}

with probability at least $1-c_1\exp(-c_2n)$, for some $c_1,c_2>0$. The result (<ref>) follows from the basic arithmetic inequality $2ab\leq (a+b)^2$.

§.§ Proof of Theorem <ref>

First, we address the $\ell_1$ and $\ell_2$ error bounds for the non-convex estimator. We characterize the $\ell_1$ and $\ell_2$ error bounds of a stationary point following similar lines as in the proof of Theorem 1 in Loh, 2017, which established the result with a different tolerance function and penalty. Since $ \beta_0 $ is feasible, by the first order optimality condition, we have the following inequality

\begin{equation*}
\langle \triangledown \L_n(\widetilde{\beta}_\ell^H) +\lambda v(\widetilde{\beta}_\ell^H),\beta_0 - \widetilde{\beta}_\ell^H\rangle \geq 0,
\end{equation*}

for $v(\widetilde{\beta}_\ell^H) \in \partial \|\widetilde{\beta}_\ell^H\|_1$. We let $ \widetilde{\Delta} := \widetilde{\beta}_\ell^H - \beta_0 $. By applying RSC condition (<ref>),

\begin{equation*}
\alpha_\ell \|\widetilde{\Delta}\|_2^2 -\tau_{\ell}  \sqrt{\frac{\log p}{n}}\|\widetilde{\Delta}\|_1+\langle \triangledown \L_n(\beta_0) +\lambda v(\widetilde{\beta}_\ell^H),\widetilde{\beta}_\ell^H-\beta_0 \rangle \leq 0,
\end{equation*}

By convexity of $\|\cdot\|_1$,

\begin{equation}
\lambda\|\beta_0\|_1 - \lambda\|\widetilde{\beta}_\ell^H\|_1 \geq -\lambda v(\widetilde{\beta}_\ell^H)^\top \widetilde{\Delta}.
\end{equation}

\begin{equation*}
\alpha_\ell\|\widetilde{\Delta}\|_2^2 -\tau_\ell \sqrt{\frac{\log p}{n}}\|\widetilde{\Delta}\|_1+\langle \triangledown \L_n(\beta_0) ,\widetilde{\beta}_\ell^H-\beta_0 \rangle + \lambda(\|\widetilde{\beta}_\ell^H\|_1 -\|\beta_0\|_1)\leq 0,
\end{equation*}

That is,

\begin{align*}
\alpha_\ell\|\widetilde{\Delta}\|_2^2 &\leq \tau_\ell\sqrt{\frac{\log p}{n}} \|\widetilde{\Delta}\|_1+|\langle \triangledown \L_n(\beta_0) ,\widetilde{\beta}_\ell^H-\beta_0 \rangle| + \lambda(\|\beta_0\|_1-\|\widetilde{\beta}_\ell^H\|_1)\\
&\leq \tau_\ell\sqrt{\frac{\log p}{n}} \|\widetilde{\Delta}\|_1+\|\triangledown \L_n(\beta_0)\|_\infty \|\widetilde{\Delta}\|_1 + \lambda (\|\widetilde{\Delta}_S\|_1 - \|(\widetilde{\beta}_\ell^H)_{S^c}\|_1)
\end{align*}

Since $\tau_\ell \sqrt{\frac{\log p}{n}} +\|\triangledown \L_n(\beta_0)\|_\infty\leq \frac{\lambda}{2} $,

\begin{align*}
\alpha_\ell\|\widetilde{\Delta}\|_2^2&\leq \frac{\lambda}{2} (\|\widetilde{\Delta}_S\|_1+\|\widetilde{\Delta}_{S^c}\|_1) + \lambda (\|\widetilde{\Delta}_S\|_1 - \|(\widetilde{\beta}_\ell^H)_{S^c}\|_1)\\
& = \frac{3\lambda}{2}\|\widetilde{\Delta}_S\|_1-\frac{\lambda}{2}\|\widetilde{\Delta}_{S^c}\|_1.
\end{align*}

In particular,

\begin{align}
&\alpha_\ell\|\widetilde{\Delta}\|_2^2 \leq \frac{3\lambda}{2}\|\widetilde{\Delta}_S\|_1 \leq \frac{3\sqrt{s_0}\lambda}{2}\|\widetilde{\Delta}\|_2,\label{eq:l2}\\
& \|\widetilde{\Delta}_{S^c}\|_1\leq 3\|\widetilde{\Delta}_S\|_1\label{eq:cone}
\end{align}

$\ell_2$ bound follows from (<ref>) and

\begin{align*}
\|\widetilde{\Delta}\|_1 =	\|\widetilde{\Delta}_S\|_1 +\|\widetilde{\Delta}_{S^c}\|_1 	\leq 4\|\widetilde{\Delta}_S\|_1  \leq 4\sqrt{s_0} \|\widetilde{\Delta}\|_2.
\end{align*}

Now, we address the $\ell_1$ and $\ell_2$ error bounds for the convex estimator. To do so, we need to establish a different RSC condition, introduced by Negahban et al., 2012 as follows:

For a given set $\mathbb{S}$, the loss function $\L_n$ satisfies restricted strong convexity (RSC) with parameter $\alpha > 0$ if

\begin{align}\label{def:RSC2}
\L_n(\beta) -\L_n(\beta_0) - \langle \triangledown \L_n(\beta_0), \beta- \beta_0 \rangle \geq \alpha \| \beta - \beta_0\|_2^2 \quad \mbox{for all } \beta - \beta_0 \in \mathbb{S}.
\end{align}

In the following Lemma <ref>, we show that the RSC condition <ref> with $\tau_{n,p}(t) = \tau (\log p/n) t^2$ and $\Omega = \B_2(\delta;\beta_0)$ implies the RSC condition in Negahban et al., 2012.

The RSC condition <ref> with $\tau_{n,p}(t) = \tau (\log p/n) t^2$ and $\Omega = \B_2(\delta;\beta_0)$ implies (<ref>) with parameter $\alpha/4$ and

$$\mathbb{S} = \{\Delta\in \R^p; \|\Delta_{S^c}\|_1 \leq 3\|\Delta_S\|_1\} \cap \{\Delta\in \R^p; \|\Delta\|_2 \leq \delta\},$$

where $ S \subseteq \{1,\dots,p\}$ is the support of $\beta_0$ and $s_0 := |S|$, given the sample size $n \geq (32\tau s_0/\alpha)\log p$.

Provided that Lemma <ref> is true and given the condition of $\lambda_s$ in Theorem <ref>, the $\ell_2$ error bound

\begin{align}\label{supp_eq:l2}
\| \widehat{\beta}_s^H -\beta_0\|_2 \leq  \frac{8\sqrt{s_0}\lambda_s}{\alpha_s}
\end{align}

can be obtained by applying Theorem 1 in Negahban et al., 2012. Also it is well known that an error vector $\widehat{\beta} - \beta_0$, where $\widehat{\beta}$ is a solution of Lasso optimization problem, belongs to the cone $ \{\Delta\in \R^p; \|\Delta_{S^c}\|_1 \leq 3\|\Delta_S\|_1\}$. Thus $\|\widehat{\beta}_s^H-\beta_0\|_1 \leq 4\|(\widehat{\beta}_s^H-\beta_0)_{S}\|_1 \leq 4 \sqrt{s_0} \|\widehat{\beta}_s^H-\beta_0\|_2 $. Applying this inequality to (<ref>) gives an $\ell_1$ bound. Now we present the proof of Lemma <ref>.

For any $\beta$ such that $\beta -\beta_0 \in \mathbb{S}$, we have,

\begin{align}
\L_n(\beta) &= \L_n(\beta_0) + \int \triangledown \L_n(\beta_0 + t(\beta - \beta_0))^\top (\beta - \beta_0) dt \nonumber \\
&= \L_n(\beta_0) + \triangledown \L_n(\beta_0)^\top (\beta - \beta_0) +\int_0^1 \frac{1}{t} (\triangledown \L_n(\beta_0 + t(\beta - \beta_0))-\triangledown \L_n(\beta_0))^\top t(\beta - \beta_0) dt \label{eq:supp_thm5.1-1} .
\end{align}

By the RSC condition <ref> with $\tau_{n,p}(t) = \tau (\log p/n) t^2$ and $\Omega = \B_2(\delta;\beta_0)$, for any $\beta \in \B_2(\delta;\beta_0)$ it holds that

\begin{align}
(\triangledown \L_n(\beta_0 + t(\beta - \beta_0))-\triangledown \L_n(\beta_0))^\top t(\beta - \beta_0)  \geq t^2 \left( \alpha\|\beta-\beta_0\|_2^2 -\tau \left(\frac{\log p}{n}\right) \|\beta-\beta_0\|_1^2 \right). \label{eq:supp_thm5.1-2}
\end{align}

Applying (<ref>) to (<ref>),

\begin{align*}
\L_n(\beta)- \L_n(\beta_0) - \triangledown \L_n(\beta_0)^\top (\beta - \beta_0) &\geq\int_0^1 t \left( \alpha\|\beta-\beta_0\|_2^2 -\tau \left(\frac{\log p}{n}\right) \|\beta-\beta_0\|_1^2 \right) dt\\
&= \frac{\alpha}{2}\|\beta-\beta_0\|_2^2 -\frac{\tau}{2} \left(\frac{\log p}{n}\right) \|\beta-\beta_0\|_1^2.
\end{align*}

Since $\beta -\beta_0 \in \mathbb{S}$, $\|\beta- \beta_0\|_1 \leq 4\sqrt{s_0}\|\beta- \beta_0\|_2$. Therefore,

\begin{align*}
\L_n(\beta)- \L_n(\beta_0) - \triangledown \L_n(\beta_0)^\top (\beta - \beta_0) & \geq \left( \frac{\alpha}{2} -8 \tau s_0 \frac{\log p}{n} \right)\|\beta-\beta_0\|_2^2 \geq \frac{\alpha}{4} \|\beta-\beta_0\|_2^2
\end{align*}

where the last inequality is from a given sample condition $n \geq (32 \tau s_0/\alpha)\log p$.

§.§ Proof of Corollary <ref>

The Corollary <ref> essentially follows from Proposition <ref>, Proposition <ref>, and Theorem <ref>. The main conditions to verify are $\|\triangledown \L_n^\ell(\beta_0)\|_\infty, \|\triangledown \L_n^s(\beta_0)\|_\infty = O(\sqrt{\frac{\log p}{n}})$ with high probability and Assumption A<ref>, since we have already shown that Assumption A<ref> is satisfied for the noisy labels problem in the proof of Corollary <ref>.

We first address bounds for $\|\triangledown \L_n^\ell(\beta_0)\|_\infty$ and $\|\triangledown \L_n^s(\beta_0)\|_\infty$. We note that $\| \triangledown \L_n(\beta_0)\|_\infty$, for $\L_n \in (\L_n^\ell, \L_n^s)$, has the form

\begin{align*}
\|\triangledown \L_n(\beta_0) \|_\infty = \max_{1\leq j\leq p} \left\lvert \frac{1}{n} \sum_{i=1}^n \xi_{ij}  \right\rvert,
\end{align*}

where $\xi_{ij} = \{(A'(h_{LN}(\x_i^\top \beta_0))-\z_i) h_{LN}'(\x_i^\top \beta_0)\}\x_{ij}$ if $\L_n = \L_n^\ell$, and $ \xi_{ij} = \{A'(\x_i^\top \beta_0)-T(\z_i) \}\x_{ij}$ if $\L_n = \L_n^s$. Also $\E[\xi_{ij}]=0, \forall i,j$ and $(\xi_{ij})_{i=1}^n$ are independent for any $j \in \{1,\dots,p\}$.

From Lemma <ref>, we have $|(A'(h_{LN}(\x_i^\top \beta_0))-\z_i)h_{LN}'(\x_i^\top \beta_0)| \leq 1$ and $ |A'(\x_i^\top \beta_0)-T(\z_i)| \leq 1$ a.s. Thus $\E[|\xi_{ij}|^{k}]^{1/k} \leq \E[|\x_{ij}|^k]^{1/k} \leq  \sqrt{k} K_X$ for any $k\geq 1$ by Assumption A<ref>'. In particular, $\xi_{ij}$ is mean-zero sub-gaussian with parameter $c K_X$ where $c>0$ is an absolute constant. Therefore, by Lemma <ref>, $\|\triangledown \L_n(\beta_0) \|_\infty \leq c'K_X\sqrt{\frac{\log p}{n}}$ with probability at least $1-1/p^7$ for a different constant $c'>0$.

Now we show that Assumption A<ref> holds. We recall $\ell''(t,z) = \rho_I(t) + \rho_R(t,z)$ for $\rho_I(t) = A''(h_{LN}(t))h'_{LN}(t)^2$, $\rho_R(t,z) = (A'(h_{LN}(t))-z)h''_{LN}(t)$ where $A(t) = \log (1+ \exp(t))$ and $h_{LN}(\cdot)$ defined in Section <ref>. In the following, we show that both $\sup_t |\rho_I(t)t|$ and $\sup_t |\rho_R(t,z)t|$ are bounded by an absolute constant. First, we let $a = 1-\rho_1-\rho_0$, $b = \rho_0$.

\begin{align*}
h'_{LN}(t) = \frac{ a\mu(t) (1-\mu(t))}{ (a \mu(t)+b) (1-a\mu(t)-b)},
\end{align*}

we have,

\begin{align*}
t\rho_I(t) &= tA''(h_{LN}(t)) h_{LN}'(t)^2\\
& = t (a\mu(t)+b)(1-a\mu(t)-b) \left(   \frac{a \mu(t) (1-\mu(t)) }{ (a \mu(t)+b) (1-a\mu(t)-b)}\right)^2\\
& = a t\mu(t) (1-\mu(t)) h'_{LN}(t).
\end{align*}

By Lemma <ref>, $\|h'_{LN}\|_\infty\leq 1$. Also, with an elementary calculation, it can be shown that

\begin{align*}
|t\mu(t)(1-\mu(t))| = \frac{|t|e^t}{(1+e^t)^2} \leq 2, \forall t.
\end{align*}

Therefore, $\sup_t |\rho_I(t)t| \leq 2$. Now we address $\sup_t |\rho_R(t,z)t|$. Since $|A'(h_{LN}(t))-z|\leq 1$ for all $t$ and $z \in \{0,1\}$, we have,

\begin{align*}
|t\rho_R(t,z)| = |(A'(h_{LN}(t))-z)h''(t)t|
\leq |h''(t)t|.
\end{align*}

Therefore, it is sufficient to bound $h''(t)t$. Note if $\rho_1=\rho_0=0$, $h''(t)=0$. Therefore $th''(t)$ is trivially bounded. Otherwise, we discuss three cases separately: 1. $\rho_1, \rho_0 >0$, 2. $\rho_1 >0, \rho_0 = 0$, and 3. $\rho_1=0, \rho_0>0$.

First, we note from the proof of Lemma <ref>, we have,

\begin{align*}
th''_{LN}(t) = t h_{LN}'(t)\{ 1- 2\mu(t) - h_{LN}'(t)(1-2(a\mu(t)+b))\}.
\end{align*}

Case 1: $\rho_1, \rho_0 >0$

In this case, $\sup_t|th'_{LN}(t)| <\infty$, since

\begin{align}\label{eq:cor5.1-1}
\sup_t|th'_{LN}(t)| \leq  \frac{a\sup_t| t\mu(t) (1-\mu(t)) |}{\inf_t (a \mu(t)+b) (1-a\mu(t)-b)} \leq \frac{2a}{\inf_{(\rho_0 \wedge \rho_1)\leq p\leq 1-(\rho_0 \wedge \rho_1)}x(1-x)}<\infty.
\end{align}

Also, $ |1- 2\mu(t) - h_{LN}'(t)(1-2(a\mu(t)+b) | \leq 1+ \|h_{LN}'\|_\infty \leq 2$.

For Case 2 and 3, we cannot use the bound (<ref>) since the denominator becomes zero. With elementary calculations, we can obtain

\begin{align}\label{eq:cor5.1-2}
%&=th'_{LN}(t)\{1-2\mu(t) -h_{LN}'(t)(1-2(a\mu(t)+b)) \}\\
&=-\frac{a(1-b-a)t\mu(t)^2(1-\mu(t))}{ (a \mu(t)+b) (1-a\mu(t)-b)^2}  +\frac{ abt\mu(t)(1-\mu(t))^2}{(a \mu(t)+b)^2(1-a\mu(t)-b)}
\end{align}

Case 2: $\rho_1 >0, \rho_0 = 0$

Equivalently, $b=0, a=1-\rho_1$, therefore the second term in (<ref>) does not exist, and

\begin{align*}
th''_{LN}(t)=-\frac{(1-a)t\mu(t)(1-\mu(t))}{ (1-a\mu(t))^2}  \end{align*}

Therefore $|th''_{LN}(t) |\leq 2/(1-a) = 2/\rho_1$.

Case 3: $\rho_1 =0, \rho_0 >0$

In Case 3, $a=1-\rho_0, b= \rho_0, a+b =1$. The first term in (<ref>) does not exist, and

\begin{align*}
th''_{LN}(t)=\frac{ bt\mu(t)(1-\mu(t))}{(a \mu(t)+b)^2},
\end{align*}

noting $1-a\mu(t)-b = a(1-\mu(t))$. Therefore, $|th''_{LN}(t) |\leq 2/b = 2/\rho_0$.

§.§ Proof of Theorem <ref>

First, for a given $\psi$, we let $\widehat{\beta}^{\textnormal{db}} = \widehat{\beta}^{\textnormal{db}}(\psi)$, $\widehat{\Theta} = \widehat{\Theta}(\psi)$, and $\Theta = \Theta(\psi)$ for ease of notation. For any fixed $j \in \{1,\dots,p\}$, we have

\begin{align}\label{eq:de-basing_estimator}
\widehat{\beta}^{\textnormal{db}}_j -\beta_{0j} &= \widehat{\beta}_j-\beta_{0j} -\widehat{\Theta}_j^\top  \left( \frac{1}{n}\sum_{i=1}^n \psi(\x_i^\top \widehat{\beta},\z_i)\x_i\right).
\end{align}

Let $\widehat{\Delta}:= \widehat{\beta}-\beta_0$. By the Taylor expansion,

\begin{align*}
\widehat{\Theta}_j^\top  &\left( \frac{1}{n}\sum_{i=1}^n \psi(\x_i^\top \widehat{\beta},\z_i)\x_i\right)\\
&= n^{-1}\sum_{i=1}^n \left( \psi(\x_i^\top \beta_0,\z_i)+ \psi'(v_i,\z_i)(\x_i^\top \widehat{\beta}-\x_i^\top \beta_0)\right)\widehat{\Theta}_j^\top  \x_i\\
&=n^{-1}\sum_{i=1}^n \left( \psi(\x_i^\top \beta_0,\z_i)+ \psi'(\x_i^\top \widehat{\beta},\z_i)\x_i^\top \widehat{\Delta}+\{\psi'(v_i,\z_i)-\psi'(\x_i^\top \widehat{\beta},\z_i)\}\x_i^\top \widehat{\Delta}\right)\widehat{\Theta}_j^\top \x_i
\end{align*}

for $v_i$ such that $|v_i -\x_i^\top \widehat{\beta}| \leq |\x_i^\top (\widehat{\beta} - \beta_0)|$.

First, we address the last term and show that it is $o_p(n^{-1/2})$.

\begin{align}\label{eq:28}
&n^{-1}\sum_{i=1}^n \{\psi'(v_i,\z_i)-\psi'(\x_i^\top \widehat{\beta},\z_i)\}\x_i^\top \widehat{\Delta}\widehat{\Theta}_j^\top  \x_i\nonumber \\
&\leq  n^{-1}\sum_{i=1}^n |\psi'(v_i,\z_i)-\psi'(\x_i^\top \widehat{\beta},\z_i)||\x_i^\top \widehat{\Delta}| |\widehat{\Theta}_j^\top  \x_i|
\end{align}

From A<ref>, $\psi'(t,z)$ is Lipschitz in $t$ with the Lipschitz constant $2L_\psi$,$\forall z$. Thus we have,

\begin{align}\label{eq:29}
|\psi'(v_i,\z_i)-\psi'(\x_i^\top \widehat{\beta},\z_i)| \leq 2L_\psi |v_i-\x_i^\top \widehat{\beta}|\leq 2L_\psi |\x_i^\top \beta_0-\x_i^\top \widehat{\beta}|,
\end{align}

and by combining (<ref>), (<ref>), we obtain

\begin{align*}
\frac{1}{n}\sum_{i=1}^n (\psi'(v_i,\z_i)-\psi'(\x_i^\top \widehat{\beta},\z_i))\x_i^\top \widehat{\Delta}\widehat{\Theta}_j^\top  \x_i
&\leq \frac{2L_\psi}{n} \sum_{i=1}^n (\x_i^\top \widehat{\Delta})^2|\widehat{\Theta}_j^\top  \x_i|\\
&\leq \frac{2L_\psi}{n}\| \X\widehat{\Delta}\|_2^2  \max_{1\leq i \leq n} |\widehat{\Theta}_j^\top  \x_i|.
\end{align*}

To bound $\| \X\widehat{\Delta}\|_2^2$, we use the following result, which can be obtained by combining Lemma 12 and 15 in Loh and Wainwright, 2012.

Suppose $\x_i$ satisfies the sub-gaussian tail condition with the parameter $K_X$, for all $i=1,\dots,n$. For any $u >0$, the following inequality holds with probability at least $1 - 2\exp(- c'n u (1 \wedge u)/2)$,

\begin{align}
\sup_{\|v\|_1\leq \sqrt{s(u)} \|v\|_2}\left\lvert v^\top \left(\sum_{i=1}^n\frac{\x_i\x_i^\top }{n}-\E(\x_i\x_i^\top )  \right)v\right\rvert \leq 27 u K_X^2 \|v\|_2^2
\end{align}

where $ s(u): = (c'n/4 \log p) (u \wedge u^2)$ and $c'$ is a universal constant in Bernstein's inequality (see Corollary 2.8.3 in Vershynin, 2018), given a sufficient sample size $n \geq (4\log p /c') \max \{(u\wedge u^2), (u\wedge u^2)^{-1}\}$.

Then from an application of Lemma <ref>, we have
\begin{align}\label{eq:quadratic_emp_bound}
\frac{1}{n} \sum_{i=1}^n (\x_i^\top \Delta)^2	&\leq \alpha' \|\Delta\|_2^2 + \tau' \frac{\log p}{n } \|\Delta\|_1^2, \quad \forall \Delta \in \R^p
\end{align}

with probability at least $1-2\exp(-c'n)$
where $\alpha' , \tau' $, and $c'$ are constants which only depend on model parameter $K_X$ and not dimensions $(n,p)$.
Thus we have $ \|\X\widehat{\Delta}\|_2^2/n = O_p(s_0(\log p/n))+O_p(s_0^2(\log p/n)^2) = o_p(n^{-1/2})$ by the rate assumption of $s_0$ in A<ref>. Also,

\begin{align*}
\max_{1\leq i \leq n} | \x_i^\top \widehat{\Theta}_j|
&\leq \max_{1\leq i \leq n}|\x_i^\top  (\widehat{\Theta}_j-\Theta_j)| +\max_{1\leq i \leq n}|\x_i^\top \Theta_j|\\
&\leq \max_{1\leq i \leq n}\|\x_i\|_\infty \|\widehat{\Theta}_j-\Theta_j\|_1 + \|\X \Theta_j\|_\infty =O_p(1).
\end{align*}

It holds because $\max_{i,j} |\x_{ij}| \leq C_X$ by A<ref>', $\|\widehat{\Theta}_j-\Theta_j\|_1=o_p(\sqrt{1/\log p)}$ from the assumption about $\widehat{\Theta}$, and $\|\X \Theta_j\|_\infty =O_p(1)$ from A<ref>. Therefore,

\begin{align}\label{eq:82}
\frac{1}{n}\| \X\widehat{\Delta}\|_2^2  \|\X\widehat{\Theta}_j\|_\infty = o_p(n^{-1/2}),
\end{align}

and we have,

\begin{align}\label{eq:31}
\widehat{\Theta}_j^\top  \psi_n(\widehat{\beta})
=\frac{1}{n} \sum_{i=1}^n \left( \psi(\x_i^\top \beta_0,\z_i)+ \psi'(\x_i^\top \widehat{\beta},\z_i)\x_i^\top \widehat{\Delta}\right)\widehat{\Theta}_j^\top \x_i+o_p(n^{-1/2}).
\end{align}

Combining (<ref>) with (<ref>),

\begin{align*}
\widehat{\beta}^{\textnormal{db}}_j -\beta_{0j}
&= \widehat{\beta}_j-\beta_{0j} - n^{-1}\sum_{i=1}^n \left( \psi(\x_i^\top \beta_0,\z_i)+ \psi'(\x_i^\top \widehat{\beta},\z_i)\x_i^\top \widehat{\Delta}\right)\widehat{\Theta}_j^\top \x_i+o_p(n^{-1/2})\\
&= e_j^\top  \widehat{\Delta}-\widehat{\Theta}_j^\top \psi_n(\beta_0)- n^{-1}\sum_{i=1}^n \left( \psi'_I(\x_i^\top \widehat{\beta})+\psi'_R(\x_i^\top \widehat{\beta},\z_i)\right)\widehat{\Theta}_j^\top \x_i\x_i^\top \widehat{\Delta}+o_p(n^{-1/2}),
\end{align*}

where we use the relationship $\psi'(t,z) = \psi_I'(t) + \psi'_R(t,z)$ in (<ref>).
Recalling the definition
$\psi'_{I,n}(\beta) := n^{-1} \sum_{i=1}^n \psi_I'(\x_i^\top \beta)\x_i\x_i^\top $,

\begin{align*}
n^{-1}\sum_{i=1}^n \psi'_I(\x_i^\top \widehat{\beta})\widehat{\Theta}_j^\top \x_i\x_i^\top \widehat{\Delta} =\widehat{\Theta}_j^\top \left( n^{-1}\sum_{i=1}^n \psi'_I(\x_i^\top \widehat{\beta})\x_i\x_i^\top \right)\widehat{\Delta} = \widehat{\Theta}_j^\top \psi'_{I,n}(\widehat{\beta})\widehat{\Delta}
\end{align*}

thus we have

\begin{align*}
\widehat{\beta}^{\textnormal{db}}_j -\beta_{0j} = -\widehat{\Theta}_j^\top \psi_n(\beta_0) -\underbrace{ n^{-1}\sum_{i=1}^n \psi'_R(\x_i^\top \widehat{\beta},\z_i)\widehat{\Theta}_j^\top \x_i\x_i^\top \widehat{\Delta}}_\textrm{Term-I} + \underbrace{\widehat{\Delta}^\top (e_j - \psi'_{I,n}(\widehat{\beta})\widehat{\Theta}_j)}_\textrm{Term-II}+o_p(n^{-1/2}).
\end{align*}

We will show that the first term $\sqrt{n} \widehat{\Theta}_j^\top \psi_n(\beta_0)$  will converge to the normal distribution. Both remainder terms (Term-I and Term-II) need to be $o_p(n^{-1/2})$. For the second remainder term (Term-II), we have $|\widehat{\Delta}^\top (e_j - \psi'_{I,n}(\widehat{\beta})\widehat{\Theta}_j)| \leq
\|\widehat{\Delta}\|_1 \|e_j -\psi'_{I,n}(\widehat{\beta})\widehat{\Theta}_j\|_\infty =O_p(s_0\sqrt{\log p/n})O_p(\sqrt{\log p/n}) = o_p(n^{-1/2})$ by the rate condition A<ref> and the assumptions in the theorem. Now we address the first remainder term (Term-I):

\begin{align}\label{eq:term1}
&n^{-1}\sum_{i=1}^n \psi'_R(\x_i^\top \widehat{\beta},\z_i)\widehat{\Theta}_j^\top \x_i\x_i^\top \widehat{\Delta}\nonumber\\
&=n^{-1}\sum_{i=1}^n \left\lbrace \psi'_R(\x_i^\top \beta_0,\z_i)+\left(\psi'_R(\x_i^\top \widehat{\beta},\z_i)-\psi'_R(\x_i^\top \beta_0,\z_i)\right)\right\rbrace\widehat{\Theta}_j^\top \x_i\x_i^\top \widehat{\Delta}.
\end{align}

We need the following Lemma which establishes a kind of sparse eigenvalue condition.

Let $E \in \R^{n\times n}$ be a random matrix which has a representation $E = \frac{1}{n}\sum_{i=1}^n e_i \x_i\x_i^\top $, for random $(e_i)_{i=1}^n$ such that $\E[e_i|\x_i] = 0$ and $|e_i| \leq c_e$ a.s., and $\x_i$ satisfies the sub-gaussian tail condition with the parameter $K_X$ for all $i$.  Then for any $s,s'\geq 1,$ if $n\geq C (s+s')\log p$ for an absolute constant $C$, there exist constants $c_1, c_2>0$ such that

\begin{align*}
P\left( \sup_{\substack{ u \in \B_1(\sqrt{s}) \cap \B_2(1), \\ v \in \B_1(\sqrt{s'}) \cap \B_2(1)}}|u^\top  E v|    \geq  c_1 \sqrt{(s+s') \frac{\log p}{n}} \right) \leq  \frac{c_2}{p^{s+s'}}.
\end{align*}

The proof of the Lemma is presented at the end of this section. Now we apply Lemma <ref> to show that $n^{-1}\sum_{i=1}^n \psi'_R(\x_i^\top \widehat{\beta},\z_i)\widehat{\Theta}_j^\top \x_i\x_i^\top \widehat{\Delta}$ is $o_p(n^{-1/2})$. We have,

\begin{align*}
n^{-1}\sum_{i=1}^n \psi'_R(\x_i^\top \beta_0,\z_i )\widehat{\Theta}_j^\top \x_i\x_i^\top \widehat{\Delta} = \widehat{\Theta}_j^\top  \left(n^{-1}\sum_{i=1}^n \psi'_R(\x_i^\top \beta_0,\z_i )\x_i\x_i^\top \right)\widehat{\Delta} = \widehat{\Theta}_j^\top  E^R\widehat{\Delta}
\end{align*}

where we define $E^R:=n^{-1}\sum_{i=1}^n \psi'_R(\x_i^\top \beta_0,\z_i )\x_i\x_i^\top $. From the condition of $\widehat{\beta}$ in Theorem <ref>, we have  $\widehat{\Delta} /\|\widehat{\Delta} \|_2 \in \B_1(\sqrt{c s_0}) \cap \B_2(1)$ for a constant $c>0$. Also, $\|\widehat{\Theta}_j\|_1 \leq \|\widehat{\Theta}_j - \Theta_j\|_1+ \|\Theta_j\|_1$ and $\|\widehat{\Theta}_j\|_2 \geq \|\Theta_j\|_2-\|\widehat{\Theta}_j - \Theta_j\|_2\geq  \|\Theta_j\|_2-\|\widehat{\Theta}_j - \Theta_j\|_1 $. Define an event $\mathcal{E}_n:= \{\|\widehat{\Theta}_j - \Theta_j\|_1  \leq 0.5\|\Theta_j\|_2\}$.

\begin{align*}
\frac{\|\widehat{\Theta}_j\|_1 }{\|\widehat{\Theta}_j\|_2} \leq \frac{ \|\Theta_j\|_1+\|\widehat{\Theta}_j - \Theta_j\|_1}{\|\Theta_j\|_2-\|\widehat{\Theta}_j - \Theta_j\|_1} \leq 3 \frac{ \|\Theta_j\|_1}{\|\Theta_j\|_2}
\end{align*}

on $\mathcal{E}_n$. We note that $\Theta_j$ is at most $s_*+1$ sparse vector, recalling the definition $s_* := \max_{1\leq j \leq p} \|\Theta_{j,-j}\|_0$. Also, $\|\Theta\|_2 \asymp 1$, since $\|\Theta\|_2 = \lambda_{\textnormal{min}} ^{-1}(\E[\psi'_I(\x^\top\beta_0)\x\x^\top])$ and the minimum eigenvalue of $\E[\psi'_I(\x^\top\beta_0)\x\x^\top]$ can be shown to be bounded above and also bounded below by a positive constant. More concretely, for any unit vector $u$,

\begin{align*}
u^T \E [\psi_I'(\x^T\beta_0)\x\x^\top] u \geq   \E [\psi_I'(\x^\top\beta_0)(\x^\top u)^2 \mathbbm{1} \{ |\x^\top \beta_0 | \leq \tau_c\}]\geq \inf_{|t|\leq \tau_c} \psi'_I(t) C_\lambda/2,
\end{align*}

\begin{align*}
u^T \E [\psi_I'(\x^T\beta_0)\x\x^\top] u \leq C_\psi \E[(\x^\top u)^2] \leq 2C_\psi K_X^2
\end{align*}

for $\tau_c := (2 c_b^2 K_X^2 \log (16K_X^2/C_\lambda))^{1/2}$ using Lemma <ref>, Assumptions A<ref>' and A<ref>, where $c_b$ is a constant such that $\|\beta_0\|_2 \leq c_b$, which exists by the condition $\|\beta_0\|_2= O(1)$.

Thus $\|\Theta_j\|_1 \leq \sqrt{ s_*+1 } \|\Theta_j\|_2$, $\widehat{\Theta}_j/\|\widehat{\Theta}_j\|_2  \in \B_1(\sqrt{9(s_*+1)}) \cap \B_2(1)$ on $\mathcal{E}_n$. Also, we have $\P(\mathcal{E}_n) \underset{n}{\rightarrow} 1$ by $\| \widehat{\Theta}_j - \Theta_j\|_1 = o_p(1/\sqrt{\log p})$ and $\|\Theta_j\|_2  \asymp 1$. Then on $\mathcal{E}_n$,

\begin{align*}
| \widehat{\Delta} ^\top   E^R \widehat{\Theta}_j| \leq \|\widehat{\Delta}\|_2 \|\widehat{\Theta}_j\|_2   \sup_{\substack{u \in \B_1(\sqrt{s}) \cap \B_2(1), \\ v \in \B_1(\sqrt{s'}) \cap \B_2(1)}} |u^\top E v| ,
\end{align*}

for $s = cs_0$ and $s' = 9(s_*+1)$. Since $\|\widehat{\Delta}\|_2 = O_p (\sqrt{s_0 \log p/n})$ and $\|\widehat{\Theta}_j\|_2   = O_p(1)$,

\begin{align*}
\|\widehat{\Delta}\|_2 \|\widehat{\Theta}_j\|_2   \sup_{\substack{u \in \B_1(\sqrt{s}) \cap \B_2(1), \\ v \in \B_1(\sqrt{s'}) \cap \B_2(1)}}|u^\top E v|
& = O_p ( \sqrt{\frac{s_0 \log p}{n}}) \cdot O_p( \sqrt{\frac{ (s_0 + s_*) \log p}{n}})= o_p(n^{-1/2})
\end{align*}

on $\mathcal{E}_n$, where the last inequality is from the rate conditions $s_0, s_*  = o(\sqrt{n}/\log p)$ from A<ref>. Since $\P(\mathcal{E}_n) \underset{n}{\rightarrow} 1$, we conclude $| \widehat{\Delta} ^\top   E^R \widehat{\Theta}_j|  = o_p(n^{-1/2})$.

For the second term in (<ref>),

\begin{align*}
&n^{-1}\sum_{i=1}^n \left\lvert\psi'_R(\x_i^\top \widehat{\beta},\z_i)-\psi'_R(\x_i^\top \beta_0,\z_i)\right\rvert|\widehat{\Theta}_j^\top \x_i||\x_i^\top \widehat{\Delta}|
\leq L_\psi \|\X\widehat{\Theta}_j\|_\infty \frac{1}{n}\|\X \widehat{\Delta}\|_2^2
\end{align*}

where we use A<ref> that $\psi'_R(t,z)$ is $L_\psi$-Lipschitz in $t$ for any $z$. Then from (<ref>), we have that the second term is $ o_p(n^{-1/2})$. Therefore, combining the results we obtain

$$n^{-1}\sum_{i=1}^n \psi'_R(x_i^\top \widehat{\beta},\z_i)\widehat{\Theta}_j^\top x_ix_i^\top \widehat{\Delta} =  o_p(n^{-1/2}).$$

So far, we have obtained,

\begin{align*}
\widehat{\beta}^{\textnormal{db}}_j -\beta_{0j} =-\widehat{\Theta}_j^\top \psi_n(\beta_0) +o_p(n^{-1/2}).
\end{align*}

It remains to show that

\begin{align*}
\frac{\sqrt{n}\widehat{\Theta}_j^\top \psi_n(\beta_0)}{\sqrt{(\Theta^\top \E[\psi(\x^\top \beta_0,\z)^2\x\x^\top ] \Theta})_{jj}} \overset{d}{\rightarrow} \mathcal{N}(0,1).
\end{align*}

By CLT,

\begin{align*}
\frac{1}{\sigma \sqrt{n}}\sum_{i=1}^n \psi(\x_i^\top \beta_0,\z_i)\x_i^\top \Theta_j \rightarrow \mathcal{N}(0,1)
\end{align*}

\begin{align*}
\sigma^2 &= \textnormal{Var}(\psi(\x^\top \beta_0,\z)\x^\top \Theta_j) =  \E[\psi(\x^\top \beta_0,\z)^2(\x^\top \Theta_j)^2]
\end{align*}

since  $\E[\psi(\x^\top \beta_0,\z)] = 0$ by (<ref>). Thus it is sufficient to show
$\sqrt{n}\widehat{\Theta}_j^\top \psi_n(\beta_0)=\sqrt{n}\Theta_j^\top \psi_n(\beta_0) + o_p(1)$ to conclude. Indeed, we have,

\begin{align*}
-\Theta_j)^\top \psi_n(\beta_0)|
\leq \sqrt{n}\|\widehat{\Theta}_j-\Theta_j\|_1\|\psi_n(\beta_0)\|_\infty = o_p(1). \end{align*}

This holds because, by the condition of $\widehat{\Theta}$, $\|\widehat{\Theta}_j-\Theta_j\|_1= o_p(\sqrt{1/\log p})$ and $\|\psi_n(\beta_0)\|_\infty =O_p(\sqrt{\log p/n})$. Recalling the definition of $\psi_n$, we have,

\begin{align*}
\|\psi_n(\beta_0)\|_\infty =  \max_{1\leq j \leq p} \left\lvert\frac{1}{n} \sum_{i=1}^n \psi(\x_i^\top \beta_0, \z_i)\x_{ij} \right\rvert.
\end{align*}

From A<ref>, we have $\|\psi\|_\infty \leq C_\psi$. Also $\E[\psi(\x_i^\top \beta_0, \z_i)\x_{ij}]=0$ by (<ref>). Thus $\frac{1}{n}\sum_{i=1}^n\psi(\x_i^\top \beta_0, \z_i)\x_{ij}$ is mean-zero sub-gaussian with a parameter $c C_\psi K_X/\sqrt{n}$ for an absolute constant $c>0$. Thus from Lemma <ref>, $ \|\psi_n(\beta_0)\|_\infty= O_p(\sqrt{\log p/n}).$

First we establish the following inequality. For any $\tilde{s} \geq 1$, there exists $c_0>0$ which do not depend on dimensions $(n,p)$ such that

\begin{align}\label{eq:lema7-bound1}
\P\left( \sup_{u \in \B_0 (\tilde{s}) \cap \B_2(1)} |u^\top E u|  \geq c_0 \sqrt{\tilde{s} \frac{\log p}{n}}\right) \leq c_2 /p^{\tilde{s}},
\end{align}

holds where $c_2$ is an absolute constant.

Since for any unit vector $u \in \R^p$ and $i$, $\E[e_i (\x_i^\top u)^2] =0$ and $\E[|e_i(\x_i^\top u)^2|^k]^{1/k} \leq c_e \E[(\x_i^\top u)^{2k}]^{1/k} \leq 2c_eK_X^2 k$, $\forall k\geq 1$, $e_i(\x_i^\top u)^2$ is mean-zero sub-exponential whose parameter is $cc_eK_X^2$ for an absolute constant $c$. From Bernstein's inequality, for every $t\geq 0$, we have

\begin{align}\label{eq:lema7-bernstein}
\P(|u^\top  E u| \geq tc_eK_X^2) \leq \exp(-c'n (t^2 \wedge t) ),
\end{align}

where $c'>0$ is an absolute constant.

\begin{align*}
\B_0 (\tilde{s}) \cap \B_2(1)  &= \bigcup_{k=0}^{\tilde{s}}  \{ v \in \B_2(1); \|v\|_0 = k\}\\
& = \bigcup_{k=0}^{\tilde{s}} \bigcup_{S; |S| = k}  \{ v\in \B_2(1); \textnormal{supp}(v) = S\}.
\end{align*}

Taking a union bound,

\begin{align*}
\P( \sup_{u \in \B_0 (\tilde{s}) \cap \B_2(1)} |u^\top E u|  \geq t c_eK_X^2) \leq  \sum_{k=0}^{\tilde{s}} \sum_{S; |S| = k}P(\|E_{S,S}\|_2 \geq t c_eK_X^2),
\end{align*}

where $E_{S,S}$ is a sub-matrix of $E$ supported on $S$.
Letting $\mathcal{N}_\epsilon$ is an $\epsilon$-net of the sphere $\mathcal{S}^{|S|-1}$, we have

\begin{align*}
\|E_{S,S}\|_2 \leq \frac{1}{1-2\epsilon} \sup_{v \in \mathcal{N}_\epsilon} |v^\top  E_{S,S} v|
\end{align*}

by the covering argument (e.g., Vershynin, 2018). Take $\epsilon = 1/4$. Then,

\begin{align*}
\P( \sup_{u \in \B_0 (\tilde{s}) \cap \B_2(1)} |u^\top E u|  \geq t c_eK_X^2) &\leq  \sum_{k=0}^{\tilde{s}} \binom{p}{k} 9^{k}  P(|v^\top  E_{S,S} v| \geq tc_eK_X^2/2) \\
&\leq   2  \exp(-c''n (t \wedge t^2 )+\tilde{s}\log (9p)),
\end{align*}

where we use the bounds $|\mathcal{N}_{1/4}|\leq 9^{|S|}$, $\binom{p}{k} \leq p^k$, and (<ref>), and $c''$ is a universal constant. Taking $t^2 = 2\tilde{s}\log (9p) /c''n$, we have

\begin{align*}
\P( \sup_{u \in \B_0 (\tilde{s}) \cap \B_2(1)} |u^\top E u|  \geq c_eK_X^2 \sqrt{2\tilde{s}\frac{\log 9p}{n}})\leq 2/(9p^{\tilde{s}}),
\end{align*}

given a sample size condition $n \geq 2\tilde{s} \log 9p / c''$. The we obtain the inequality (<ref>) with $c_0 = 4c_e K_X^2$ and $c_2 = 2/9$, where we use the inequality $p^5 \geq 9p$ for $p \geq 2$.

Now we show that on the event that

\begin{align}\label{eq:l0bound}
\sup_{u \in \B_0 (s+s') \cap \B_2(1)} |u^\top E u|  \leq c_0 \sqrt{(s+s') \frac{\log p}{n}},
\end{align}

we have

\begin{align}\label{eq:l1bound}
\sup_{\substack{u \in \B_1(\sqrt{s}) \cap \B_2(1), \\ v \in \B_1(\sqrt{s'}) \cap \B_2(1)}} |u^\top E v|  \leq c_1 \sqrt{(s+s') \frac{\log p}{n}}
\end{align}

where $c_1$ is a multiple of $c_0$.

From Lemma 11 in Loh and Wainwright, 2012, we have

\begin{align*}
\B_1(\sqrt{s}) \cap \B_2(1) \subseteq 3 \overline{ \textnormal{conv}(\B_0(s) \cap \B_2(1))}
\end{align*}

where $\textnormal{conv}(D)$ denotes a convex hull of $D \subseteq \R^p$. Using this Lemma, for any $u \in  \B_1(\sqrt{s}) \cap \B_2(1)$ and $v \in  \B_1(\sqrt{s'}) \cap \B_2(1)$ , we have the following representation

\begin{align*}
u = \sum_{i=1}^p \alpha_i u_i \quad \mbox{and} \quad  v = \sum_{j=1}^p \beta_j v_j
\end{align*}

for $\alpha_i\geq 0, \beta_j\geq 0, u_i, v_j $ such that $\sum_i \alpha_i = \sum_j \beta_j = 1$, $u_i \in \B_0(s) \cap \B_2(3) $ and $v_j \in \B_0(s') \cap \B_2(3)$, $\forall i,j$. Then,

\begin{align*}
u^\top  E v = (\sum_{i=1}^p \alpha_i u_i )^\top  E (\sum_{j=1}^p \beta_j v_j ) = \sum_{i,j} 9\alpha_i \beta_j \tilde{u}_i^\top  E \tilde{v}_j
\end{align*}

for $\tilde{u}_i,\tilde{v}_j \in \B_0(s+s') \cap \B_2(1), \forall i,j$.

\begin{align*}
|\tilde{u}_i^\top  E \tilde{v}_j| &\leq \frac{1}{2 }\left\lbrace |(\tilde{u}_i+\tilde{v}_j)^\top  E (\tilde{u}_i+\tilde{v}_j) | + |\tilde{u}_i^\top  E \tilde{u}_i | +|\tilde{v}_j^\top  E \tilde{v}_j | \right\rbrace,
\end{align*}

by the basic inequality $2x^\top E y= (x+y)^\top E (x+y)-x^\top Ex - y^\top Ey $ for any $x,y \in \R^p$, we have

\begin{align*}
\sup_{\substack{u \in \B_1(\sqrt{s}) \cap \B_2(1), \\ v \in \B_1(\sqrt{s'}) \cap \B_2(1)}} |u^\top E v|  &\leq \sum_{i,j}  \frac{27}{2 }(\alpha_i \beta_j) \sup_{u \in \B_0 (s+s') \cap \B_2(1)} |u^\top E u|\\
&\leq \sum_{i,j} (\alpha_i \beta_j) \left( \frac{27}{2}c_0 \sqrt{(s+s')  \frac{\log p}{n}} \right) = c_1 \sqrt{(s+s') \frac{\log p}{n} }
\end{align*}

where for the second inequality we use (<ref>) and $c_1 = 27c_0/2$. Thus (<ref>) holds with probability at least $1-c_2/p^{s+s'}$.

§.§ Construction of an Approximate Inverse of Fisher Information Matrix Using Node-Wise Regression

First we let $W(\beta) := \textnormal{diag}(\{\psi'_I(\x_i^\top \beta)\}_{i=1}^n)$. We note the square root of $W(\beta)$ exists since $\psi_I(t) \geq 0$ for all $t$. Following the node-wise lasso construction in van de Geer et al., 2014, we define

\begin{align*}
\widehat{\gamma}_j &:= \argmin_{\gamma \in \R^p }\frac{1}{2n}\|W(\widehat{\beta})^{1/2}\X_j -  W(\widehat{\beta})^{1/2}\X_{-j}\gamma\|_2 +  \lambda_j \|\gamma\|_1\\
\widehat{\tau}_j^2 &:= \|W(\widehat{\beta})^{1/2}\X_j -  W(\widehat{\beta})^{1/2}\X_{-j}\widehat{\gamma}\|_2^2/n + \lambda_j \|\widehat{\gamma}_j\|_1.
\end{align*}

We construct $\widehat{\Theta}(\psi)$ by taking  $\widehat{\Theta}(\psi)_j^\top  :=\widehat{\tau}_j^{-2} [-\widehat{\gamma}_{j,1},\dots,1,-\widehat{\gamma}_{j,p}] \in \R^{1\times p}.$

Assume A<ref>', A<ref>, A<ref>-A<ref> and $\lambda_j \asymp \sqrt{\log p/n}$ for all $j$. In addition we assume there exists $C_X>0$ such that $\|\x_i\|_\infty \leq C_X$ a.s. for all $i$. Then for any $j \in \{1,\dots,p\}$, we have

\begin{align*}
\|\widehat{\Theta}_j(\psi) - \Theta_j(\psi)\|_1 &= o_p(1/\sqrt{\log p}), \qquad
\|\widehat{\Theta}_j(\psi) - \Theta_j(\psi)\|_2 = o_p(n^{-1/4}).
\end{align*}

The result follows by checking the conditions of Theorem 3.2 in van de Geer et al., 2014.

[Angluin and Laird, 1988]
D. Angluin and P. Laird.
Learning from noisy examples.
Mach. Learn., 20 (4):0 343–370, Apr. 1988.

[Beck, 2017]
A. Beck.
First-Order Methods in Optimization.
SIAM, Oct. 2017.

[Bollinger and David, 1997]
C. R. Bollinger and M. H. David.
Modeling discrete choice with response error: Food stamp
J. Am. Stat. Assoc., 920 (439):0 827–835,

[Bootkrajang and Kabán, 2012]
J. Bootkrajang and A. Kabán.
Label-Noise robust logistic regression and its applications.
In Machine Learning and Knowledge Discovery in Databases,
pages 143–158. Springer Berlin Heidelberg, 2012.

[Carroll et al., 2006]
R. J. Carroll, D. Ruppert, L. A. Stefanski, and C. M. Crainiceanu.
Measurement Error in Nonlinear Models: A Modern Perspective,
Second Edition.
Chapman and Hall/CRC, 2 edition edition, June 2006.

[Chaganty and Liang, 2014]
A. T. Chaganty and P. Liang.
Estimating Latent-Variable graphical models using moments and
In Proceedings of the 31st International Conference on Machine
Learning, volume 32 of Proceedings of Machine Learning Research,
pages 1872–1880, Bejing, China, Jan. 2014.

[Dezeure et al., 2015]
R. Dezeure, P. Bühlmann, L. Meier, and N. Meinshausen.
High-Dimensional inference: Confidence intervals, $p$-Values and
R-Software hdi.
Stat. Sci., 300 (4):0 533–558, 2015.

[Du Plessis et al., 2015]
M. Du Plessis, G. Niu, and M. Sugiyama.
Convex formulation for learning from positive and unlabeled data.
In International Conference on Machine Learning, pages
1386–1394, June 2015.

[Elkan and Noto, 2008]
C. Elkan and K. Noto.
Learning classifiers from only positive and unlabeled data.
In Proceedings of the 14th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining, KDD '08, pages 213–220,
New York, NY, USA, 2008.

[Fahrmeir and Tutz, 2001]
L. Fahrmeir and G. Tutz.
Multivariate Statistical Modelling Based on Generalized Linear
Springer Series in Statistics. Springer-Verlag New York, 2 edition,

[Fowler and Fields, 2014]
D. M. Fowler and S. Fields.
Deep mutational scanning: a new style of protein science.
Nat. Methods, 110 (8):0 801–807, Aug. 2014.

[Frénay and Verleysen, 2014]
B. Frénay and M. Verleysen.
Classification in the presence of label noise: a survey.
IEEE Trans Neural Netw Learn Syst, 250 (5):0
845–869, May 2014.

[Godambe, 1960]
V. P. Godambe.
An optimum property of regular maximum likelihood estimation.
Ann. Math. Stat., 310 (4):0 1208–1211, 1960.

[Hastie and Fithian, 2013]
T. Hastie and W. Fithian.
Inference from presence-only data; the ongoing controversy.
Ecography, 360 (8):0 864–867, Aug. 2013.

[Hausman et al., 1998]
J. A. Hausman, J. Abrevaya, and F. M. Scott-Morton.
Misclassification of the dependent variable in a discrete-response
J. Econom., 870 (2):0 239–269, Dec. 1998.

[Ipeirotis et al., 2010]
P. G. Ipeirotis, F. Provost, and J. Wang.
Quality management on amazon mechanical turk.
In Proceedings of the ACM SIGKDD Workshop on Human
Computation, HCOMP '10, pages 64–67, New York, NY, USA, 2010.

[Jain et al., 2017]
S. Jain, M. White, and P. Radivojac.
Recovering true classifier performance in positive-unlabeled
In Thirty-First AAAI Conference on Artificial
Intelligence, 2017.

[Kato, 2013]
T. Kato.
Perturbation theory for linear operators.
Springer Science & Business Media, June 2013.

[Knight and Fu, 2000]
K. Knight and W. Fu.
Asymptotics for lasso-type estimators.
Ann. Stat., 280 (5):0 1356–1378, Oct. 2000.

[Kontorovich, 2014]
A. Kontorovich.
Concentration in unbounded metric spaces and algorithmic stability.
In International Conference on Machine Learning, pages 28–36,
Jan. 2014.

[Li and Bradic, 2018]
A. H. Li and J. Bradic.
Boosting in the presence of outliers: Adaptive classification with
nonconvex loss functions.
Journal of the American Statistical Association, 1130
(522):0 660–674, 2018.

[Liu et al., 2003]
B. Liu, Y. Dai, X. Li, W. S. Lee, and P. S. Yu.
Building text classifiers using positive and unlabeled examples.
In Third IEEE International Conference on Data Mining, pages
179–186, Nov. 2003.

[Loh, 2017]
P.-L. Loh.
Statistical consistency and asymptotic normality for high-dimensional
robust $M$-estimators.
Ann. Stat., 450 (2):0 866–896, Apr. 2017.

[Loh and Wainwright, 2012]
P.-L. Loh and M. J. Wainwright.
High-dimensional regression with noisy and missing data: Provable
guarantees with nonconvexity.
Ann. Stat., 400 (3):0 1637–1664, June 2012.

[Loh and Wainwright, 2015]
P.-L. Loh and M. J. Wainwright.
Regularized m-estimators with nonconvexity: Statistical and
algorithmic theory for local optima.
J. Mach. Learn. Res., 160 (1):0 559–616, Jan.

[Lyles et al., 2011]
R. H. Lyles, L. Tang, H. M. Superak, C. C. King, D. D. Celentano, Y. Lo, and
J. D. Sobel.
Validation data-based adjustments for outcome misclassification in
logistic regression: an illustration.
Epidemiology, 220 (4):0 589–597, July 2011.

[Magder and Hughes, 1997]
L. S. Magder and J. P. Hughes.
Logistic regression when the outcome is measured with uncertainty.
Am. J. Epidemiol., 1460 (2):0 195–203, July

[McCullagh and Nelder, 1989]
P. McCullagh and J. A. Nelder.
Generalized Linear Models, Second Edition.
CRC Press, Aug. 1989.

[Mei et al., 2018]
S. Mei, Y. Bai, and A. Montanari.
The landscape of empirical risk for nonconvex losses.
Ann. Stat., 460 (6A):0 2747–2774, Dec. 2018.

[Morton, 1981]
R. Morton.
Efficiency of estimating equations and the use of pivots.
Biometrika, 680 (1):0 227–233, 1981.
ISSN 0006-3444.

[Natarajan et al., 2018]
N. Natarajan, I. S. Dhillon, P. Ravikumar, and A. Tewari.
Cost-Sensitive learning with noisy labels.
J. Mach. Learn. Res., 180 (155):0 1–33, 2018.

[Negahban et al., 2012]
S. N. Negahban, P. Ravikumar, M. J. Wainwright, and B. Yu.
A unified framework for High-Dimensional analysis of
$M$-Estimators with decomposable regularizers.
Stat. Sci., 270 (4):0 538–557, Nov. 2012.

[Nemirovski et al., 2009]
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro.
Robust stochastic approximation approach to stochastic programming.
SIAM J. Optim., 190 (4):0 1574–1609, Jan.

[Neuhaus, 1999]
J. M. Neuhaus.
Bias and efficiency loss due to misclassified responses in binary
Biometrika, 860 (4):0 843–855, 1999.

[Newey and McFadden, 1994]
W. K. Newey and D. McFadden.
Chapter 36 large sample estimation and hypothesis testing.
In Handbook of Econometrics, volume 4, pages 2111–2245.
Elsevier, Jan. 1994.

[Pepe, 1992]
M. S. Pepe.
Inference using surrogate outcome data and a validation sample.
Biometrika, 790 (2):0 355–365, June 1992.

[Raskutti et al., 2011]
G. Raskutti, M. J. Wainwright, and B. Yu.
Minimax rates of estimation for High-Dimensional linear regression
Over $\ell_q$-Balls.
IEEE Trans. Inf. Theory, 570 (10):0
6976–6994, Oct. 2011.

[Romero et al., 2015]
P. A. Romero, T. M. Tran, and A. R. Abate.
Dissecting enzyme function with microfluidic-based deep mutational
Proc. Natl. Acad. Sci. U. S. A., 1120 (23):0
7159–7164, June 2015.

[Sculley and Cormack, 2008]
D. Sculley and G. V. Cormack.
Filtering email spam in the presence of noisy user feedback.
In CEAS, 2008.

[Shao, 2003]
J. Shao.
Mathematical Statistics.
Springer Science & Business Media, July 2003.

[Singhania et al., 2013]
R. R. Singhania, A. K. Patel, R. K. Sukumaran, C. Larroche, and A. Pandey.
Role and significance of beta-glucosidases in the hydrolysis of
cellulose for bioethanol production.
Bioresour. Technol., 127:0 500–507, Jan. 2013.

[Smyth et al., 1995]
P. Smyth, U. M. Fayyad, M. C. Burl, P. Perona, and P. Baldi.
Inferring ground truth from subjective labelling of venus images.
In G. Tesauro, D. S. Touretzky, and T. K. Leen, editors,
Advances in Neural Information Processing Systems 7, pages 1085–1092.
MIT Press, 1995.

[Song and Raskutti, 2018]
H. Song and G. Raskutti.
PUlasso: High-dimensional variable selection with presence-only
J. Am. Stat. Assoc., pages 1–41, Dec. 2018.

[van de Geer et al., 2014]
S. van de Geer, P. Bühlmann, Y. Ritov, and R. Dezeure.
On asymptotically optimal confidence regions and tests for
high-dimensional models.
Ann. Statist., 420 (3):0 1166–1202, 06 2014.

[van den Hout and van der Heijden, 2002]
A. van den Hout and P. G. M. van der Heijden.
Randomized response, statistical disclosure control and
misclassification: A review.
International Statistical Review / Revue Internationale de
Statistique, 700 (2):0 269–288, 2002.

[van der Vaart, 1998]
A. W. van der Vaart.
Asymptotic Statistics.
Cambridge University Press, 1998.

[Vershynin, 2018]
R. Vershynin.
High-Dimensional Probability by Roman Vershynin.
Cambridge University Press, Sept. 2018.

[Ward et al., 2009]
G. Ward, T. Hastie, S. Barry, J. Elith, and J. R. Leathwick.
Presence-only data and the em algorithm.
Biometrics, 650 (2):0 554–563, June 2009.

[Yang et al., 2014]
P. Yang, X. Li, H.-N. Chua, C.-K. Kwoh, and S.-K. Ng.
Ensemble positive unlabeled learning for disease gene identification.
PLoS One, 90 (5):0 e97079, May 2014.


# On Perfect Hypercomplex Algebra

Daizhan Cheng, Zhengping Ji This work is supported partly by the National
Natural Science Foundation of China (NSFC) under Grants 62073315, 61074114,
and 61273013.Key Laboratory of Systems and Control, Academy of Mathematics and
Systems Sciences, Chinese Academy of Sciences, Beijing 100190, P. R. China
(e-mail<EMAIL_ADDRESS>jizhengping@amss.ac.cn).

###### Abstract

The set of associative and commutative hypercomplex numbers, called the
perfect hypercomplex algebra (PHA) is investigated. Necessary and sufficient
conditions for an algebra to be a PHA via semi-tensor product(STP) of matrices
are reviewed. The zero set is defined for non-invertible hypercomplex numbers
in a given PHA, and a characteristic function is proposed for calculating zero
set. Then PHA of different dimensions are considered. First, $2$-dimensional
PHAs are considered as examples to calculate their zero sets etc. Second, all
the $3$-dimensional PHAs are obtained and the corresponding zero sets are
investigated. Third, $4$-dimensional or even higher dimensional PHAs are also
considered. Finally, matrices over pre-assigned PHA, called perfect
hypercomplex matrices (PHMs) are considered. Their properties are also
investigated.

###### Index Terms:

Perfect hypercomplex algebra (PHA), perfect hypercomplex matrix (PHM), zero-
set, semi-tensor product (STP) of matrices.

##  I Introduction

Hypercomplex number (HN) are generalization of complex numbers
(${\mathbb{C}}$). A class of HN with pre-assigned addition and product form a
special vector space over ${\mathbb{R}}$, called a hypercomplex algebra (HA).
HAs have various applications including signal and image processing [10],
dealing with differential operators [2, abr15], designing neural networks [9],
etc.

It was proved by Weierstrass that the only finite field extension of real
numbers (${\mathbb{R}}$) is complex numbers (${\mathbb{C}}$) [8]. HA can be
considered as an extension of real numbers (${\mathbb{R}}$) to finite
dimensional algebras. We call such extension finite algebra extension of real
numbers.

In this paper we consider only a particular kind of finite algebra extensions
of ${\mathbb{R}}$, which are commutative and associative. Hence, throughout
this paper the following is assumed:

Assumption 1: $H$ is the set of PHAs, that is, the set of finite dimensional
algebras over ${\mathbb{R}}$ which are commutative and associative.

In addition to complex numbers, hyperbolic numbers, dual numbers, and
Tessarine quaternion are also PHA.

STP of matrices is a generalization of conventional matrix product. It is a
powerful tool to deal with multi-linear mappings. In [5], STP was used to
investigate finite algebra extensions of ${\mathbb{R}}$. (in fact, the
extensions of any ${\mathbb{F}}$ with $Char(F)=0$ have been discussed there.)
In [6], STP was used to investigate general Boolean-type algebras. A key issue
in these approaches is to define a matrix, called product matrix of a certain
algebra. Using STP, associativity, commutativity, and some other properties of
a finite algebra extension can be verified via its product matrix.

In this paper, this STP approach is used to investigate PHA and PHM. For PHA,
first the formulas for verifying whether an HA is associative and commutative
are reviewed. Then the zero set is defined as the set of non-invertible
numbers. A characteristic function is proposed to calculate (or characterize)
the zero set. Then the PHA of dimensions 2, 3, or 4 are constructed
separately. Even higher dimensional cases are also discussed. Their zero-sets,
which are of measure zero, are calculated. Analytic functions and some other
properties of PHAs are then discussed.

As for PHMs, their invertibility and some further properties are investigated.
The Lie-group and Lie algebra over a pre-assigned PHA, say, ${\mathcal{A}}$,
are also defined as general linear group, $GL(n,{\mathcal{A}})$ and general
linear algebra, $gl(n,{\mathcal{A}})$ are investigated. Certain properties are
revealed.

The rest of this paper is organized as follows:

Before ending this section, we give a list of notations:

  1. 1.

$H$: Set of PHAs, as finite algebra extensions over ${\mathbb{R}}$.

  2. 2.

${\mathcal{A}}_{m\times n}$: set of $m\times n$ dimensional matrices, with all
entries in algebra ${\mathcal{A}}$.

  3. 3.

$\ltimes$: STP of matrices.

  4. 4.

$\operatorname{Col}(A)$ : the set of columns (rows) of $A$;
$\operatorname{Col}_{i}(A)$ ($\operatorname{Row}_{i}(A)$): the $i$-th column
(row) of $A$.

  5. 5.

$\delta_{k}^{i}$: The $i$-th column of identity matrix $I_{k}$.

##  II Preliminaries

###  II-A Semi-tensor Product of Matrices

Since STP is a fundamental tool in this approach, this section will give a
brief survey for STP. We refer to [4] for more details. STP is a
generalization of conventional matrix product, defined as follows:

###### Definition II.1

Let $A\in{\mathbb{R}}_{m\times n}$ and $B\in{\mathbb{R}}_{p\times q}$,
$t=\operatorname{lcm}(n,p)$ be the least common multiple of $n$ and $p$. Then
the STP of $A$ and $B$, denoted by $A\ltimes B$, is defined by

$\displaystyle A\ltimes B:=\left(A\otimes I_{t/n}\right)\left(B\otimes
I_{t/P}\right),$ (1)

where $\otimes$ is Kronecker product.

It is easy to see that STP is a generalization of conventional matrix product.
That is, when $n=p$, the STP is degenerated to the conventional matrix
product, i.e.,, $A\ltimes B=AB$. Because of this, in most cases the symbol
$\ltimes$ is omitted.

One of the most important advantages of STP is that STP keeps most important
properties of conventional matrix product available, including association,
distribution, etc. In the following we introduce some additional properties of
STP, which will be used in the sequel.

Define a swap matrix $W_{[m,n]}\in{\mathcal{M}}_{mn\times mn}$ as follows:

$\displaystyle
W_{[m,n]}:=\left[I_{n}\otimes\delta_{m}^{1},I_{n}\otimes\delta_{m}^{2},\cdots,I_{n}\otimes\delta_{m}^{m},\right]\in{\mathcal{L}}_{mn\times
mn}.$ (2)

###### Proposition II.2

Let $x\in{\mathbb{R}}^{m}$ and $y\in{\mathbb{R}}^{n}$ be two column vectors.
Then

$\displaystyle W_{[m,n]}x\ltimes y=y\ltimes x.$ (3)

The following proposition “swaps” a vector with a matrix:

###### Proposition II.3

Let $x\in{\mathbb{R}}^{t}$ be a column vector, and $A$ be an arbitrary matrix.
Then

$\displaystyle x\ltimes A=(I_{t}\otimes A)\ltimes x.$ (4)

Throughout this paper the default matrix product is assumed to be STP, and the
symbol $\ltimes$ is omitted if there is no possible confusion.

###  II-B Matrix Expression of an Algebra

We are only interested in algebras over ${\mathbb{R}}$.

###### Definition II.4

[7]

  * (i)

An algebra over ${\mathbb{R}}$ is a pair, denoted by ${\mathcal{A}}=(V,*)$,
where $V$ be a real vector space, and $*:V\times V\rightarrow V$, satisfies

$\displaystyle\begin{array}[]{l}(ax+by)*z=ax*z+by*z,\\\
x*(ay+bz)=ax*y+bx*z,\quad x,y,z\in V,\;a,b\in{\mathbb{R}}.\\\ \end{array}$ (7)

  * (ii)

An algebra ${\mathcal{A}}=(V,*)$ is said to be commutative, if

$\displaystyle x*y=y*x,\quad x,y\in V.$ (8)

  * (iii)

An algebra ${\mathcal{A}}=(V,*)$ is said to be associative, if

$\displaystyle(x*y)*z=x*(y*z),\quad x,y,z\in V.$ (9)

###### Definition II.5

Let ${\mathcal{A}}=(V,*)$ be a $k$-dimensional vector space with $e=\\{{\bf
i}_{1},{\bf i}_{2},\cdots,{\bf i}_{k}\\}$ as a set of basis. Denote

$\displaystyle{\bf i}_{i}*{\bf
i}_{j}=\mathop{\sum}\limits_{s=1}^{k}c^{s}_{i,j}{\bf i}_{s},\quad
i,j=1,2,\cdots,k.$ (10)

Then the product matrix of ${\mathcal{A}}$ is defined as

$\displaystyle
P_{{\mathcal{A}}}:=\begin{bmatrix}c^{1}_{1,1}&c^{1}_{1,2}&\cdots&c^{1}_{1,k}&\cdots&c^{1}_{k,k}\\\
c^{2}_{1,1}&c^{2}_{1,2}&\cdots&c^{2}_{1,k}&\cdots&c^{2}_{k,k}\\\
~{}&~{}&\ddots&~{}&\ddots&~{}\\\
c^{k}_{1,1}&c^{k}_{1,2}&\cdots&c^{k}_{1,k}&\cdots&c^{k}_{k,k}\\\
\end{bmatrix}.$ (11)

Assume $x=\mathop{\sum}\limits_{j=1}^{k}x_{i}{\bf i}_{j}$, is expressed in a
column vector form as $x=(x_{1},x_{2},\cdots,x_{k})^{T}$. Similarly,
$y=(y_{1},y_{2},\cdots,y_{k})^{T}$. Then

###### Theorem II.6

In vector form two product of two hypercomplex numbers $x,y\in{\mathcal{A}}$
is computable via following formula.

$\displaystyle x*y=P_{{\mathcal{A}}}xy.$ (12)

Using formula (12) and the properties of STP yields the following results,
which are fundamental for our further investigation.

###### Theorem II.7

  * (i)

${\mathcal{A}}$ is commutative, if and only if,

$\displaystyle P_{{\mathcal{A}}}\left[I_{k}-W_{[k,k]}\right]=0.$ (13)

  * (ii)

${\mathcal{A}}$ is associative, if and only if,

$\displaystyle P^{2}_{{\mathcal{A}}}=P_{{\mathcal{A}}}\left(I_{k}\otimes
P_{{\mathcal{A}}}\right).$ (14)

##  III Hypercomplex Numbers

###  III-A Perfect Hypercomplex Algebra on ${\mathbb{R}}$

###### Definition III.1

[11] A number $p$ is called a hypercomplex number, if it can be expressed in
the form

$\displaystyle p=p_{0}+p_{1}{\bf i}_{1}+\cdots+p_{n}{\bf i}_{n},$ (15)

where $p_{i}\in{\mathbb{R}}$, $i=0,1,\cdots,n$, ${\bf i}_{i}$,
$i=1,2,\cdots,n$ are called hyperimaginary units.

###### Remark III.2

A hypercomplex number may belong to different algebras, depending on their
product structure matrices. A hypercomplex algebra, denoted by
${\mathcal{A}}$, is an algebra over ${\mathbb{R}}$ with basis $e=\\{{\bf
i}_{0}:=1,{\bf i}_{1},\cdots,{\bf i}_{n}\\}$.

###### Proposition III.3

Assume

${\mathcal{A}}=\\{p_{0}+p_{1}{\bf i}_{1}+\cdots+p_{n}{\bf
i}_{n}\;|\;p_{0},p_{1},\cdots,p_{n}\in{\mathbb{R}}\\}.$

Then its product matrix

$P_{{\mathcal{A}}}:=[M_{0},M_{1},\cdots,M_{n}],$

where $M_{i}\in{\mathbb{R}}_{(n+1)\times(n+1)}$, $i=0,1,\cdots,n$, satisfies
the following condition.

  * (i)

$\displaystyle M_{0}=I_{n+1}$ (16)

is an identity matrix.

  * (ii)

$\displaystyle\operatorname{Col}_{1}(M_{j})=\delta^{j+1}_{n+1},\quad
j=1,2,\cdots,n.$ (17)

###### Definition III.4

A hypercomplex algebra ${\mathcal{A}}$ is called a PHA, denoted by
${\mathcal{A}}\in\mbox{\boldmath$H$}$, if it is commutative and associative.

###### Example III.5

Consider ${\mathbb{C}}$. It is easy to calculate that its product structure
matrix is

$\displaystyle P_{{\mathbb{C}}}=\begin{bmatrix}1&0&0&-1\\\
0&1&1&0\end{bmatrix}.$ (18)

A straightforward computation verifies (13) and (14), hence it is a PHA.

###  III-B Invertibility of elements in PHA

Now for a PHA, say, ${\mathcal{A}}=(V,*)$, if every $0\neq x\in V$ has its
inverse $x^{-1}$ such that $x*x^{-1}=x^{-1}x=1$, then ${\mathcal{A}}$ is a
field. Unfortunately, according to Weierstrass, if
${\mathcal{A}}\neq{\mathbb{C}}$, it is not a field. Hence, when an element
$x\in V$ (we also say $x\in{\mathcal{A}}$, which means $x\in V$.) is
invertible.

To answer this question, we need some new concepts, which are firstly
discussed in [5].

###### Definition III.6

  * (i)

Let $A_{1},A_{2},\cdots,A_{r}$ be a set of square real matrices.
$A_{1},A_{2},\cdots,A_{r}$ are said to be jointly nonsingular, if their non-
trivial linear combination is non-singular. That is, assume

$det\left(\mathop{\sum}\limits_{i=1}^{r}c_{i}A_{i}\right)=0,$

then $c_{1}=c_{2}=\cdots=c_{r}=0$.

  * (ii)

Let $A\in{\mathbb{R}}_{k\times k^{2}}$. $A$ is said to be jointly nonsingular,
if $A=[A_{1},A_{2},\cdots,A_{k}$, where $A_{s}\in{\mathbb{R}}_{k\times k^{2}}$
and $\\{A_{i}\|i=1,2,\cdots,k\\}$ are jointly nonsingular.

Then we have the following result:

###### Proposition III.7

[5] $A\in{\mathbb{R}}_{k\times k^{2}}$ is jointly non-singular, if and only
if, one of the following two equivalent conditions is satisfied:

  * (i)

The matrix $P_{{\mathcal{A}}}x\in{\mathbb{R}}_{k\times k}$ is non-singular for
all $x\neq 0$.

  * (ii)

The following homogeneous polynomial

$\displaystyle\begin{array}[]{l}\xi(x_{1},\cdots,x_{k})=\det(Ax)\\\
~{}~{}=\mathop{\sum}\limits_{i_{1}=1}^{k}\cdots\mathop{\sum}\limits_{i_{k}=1}^{k}\mu_{i_{1},\cdots,i_{k}}x_{i_{1}}\cdots
x_{i_{k}}\neq 0,\quad\forall x\neq 0.\end{array}$ (21)

The $\xi(x_{0},x_{1},\cdots,x_{n})$ is called the characteristic function of
${\mathcal{A}}$.

###### Example III.8

Consider ${\mathbb{C}}={\mathbb{R}}(i)$. Calculating right hand side of (21)
for $P_{{\mathbb{C}}}$, we have

$xi(x_{1},x_{2})=x_{1}^{2}+x_{2}^{2}.$

Hence, $\xi(x_{1},x_{2})=0$, if and only if, $x_{1}=x_{2}=0$. It follows that
$P_{{\mathbb{C}}}$ is jointly non-singular.

Summarizing above arguments, we have the following result.

###### Proposition III.9

Let ${\mathcal{A}}$ be a finite dimensional algebra over ${\mathbb{R}}$. Then
${\mathcal{A}}$ is a field, if and only if,

  * (i)

${\mathcal{A}}$ is commutative, that is, (13) holds;

  * (ii)

${\mathcal{A}}$ is associative, that is, (14) holds;

  * (iii)

Each $0\neq x\in{\mathcal{A}}$ is invertible, that is, $P_{{\mathcal{A}}}$ is
jointly invertible.

Unfortunately, it is well known that the only finite dimensional algebra over
${\mathbb{R}}$, which is a field, is ${\mathbb{C}}$. In this paper we are
particularly interested in commutative and associative algebra
${\mathcal{A}}\in\mbox{\boldmath$H$}$. Then unless ${calA}={\mathbb{C}}$,
there must be some elements $x\neq 0$, which are not invertible.

###### Definition III.10

Let ${\mathcal{A}}\in\mbox{\boldmath$H$}$. Its zero set is defined by

$\displaystyle{\mathcal{Z}}_{{\mathcal{A}}}:=\left\\{z\in{\mathcal{A}}\;|\;\det\left(P_{{\mathcal{A}}}z\right)=0\right\\}$
(22)

It is clear that

  * (i)

if ${\mathcal{A}}={\mathbb{C}}$, then ${\mathcal{Z}}_{{\mathcal{A}}}=\\{0\\}$;

  * (ii)

if ${\mathcal{A}}\neq{\mathbb{C}}$, then
$\\{0\\}\in{\mathcal{Z}}_{{\mathcal{A}}}$, and
${\mathcal{Z}}_{{\mathcal{A}}}\backslash\\{0\\}\neq\emptyset$.

###  III-C Coordinate Transformation of Hypercomplex Algebra

Since the product matrix $P_{{\mathcal{A}}}$ of a hypercomplex algebra depends
on the basis, it is necessary to consider different forms of
$P_{{\mathcal{A}}}$ under a change of basis, which is commonly called a
coordinate transformation. Let ${\bf i}_{1},{\bf i}_{2},\cdots,{\bf i}_{n}$ be
the hyperimaginary units of ${\mathcal{A}}$ and

$\displaystyle(1,{\bf j}_{1},{\bf j}_{2},\cdots,{\bf j}_{n})=(1,{\bf
i}_{1},{\bf i}_{2},\cdots,{\bf i}_{n})T,$ (23) $\displaystyle
T=\begin{bmatrix}1&E\\\
0&T_{0}\end{bmatrix}\in{\mathbb{R}}_{(n+1)\times(n+1)},$ (24)

where $T_{0}$ is non-singular.

Then $x\in{\mathcal{A}}$ can be expressed as

$x=x_{0}+x_{1}{\bf i}_{1}+\cdots+x_{n}{\bf i}_{n}=x_{0}+\bar{x}_{1}{\bf
j}_{1}+\cdots+\bar{x}_{n}{\bf j}_{n},$

which is called a coordinate change on ${\mathcal{A}}$.

Denote $x=(x_{0},x_{1},\cdots,x_{n})^{T}$,
$\bar{x}=(\bar{x}_{0},\bar{x}_{1},\cdots,\bar{x}_{n})^{T}$. Then

$\displaystyle\bar{x}=T^{-1}x.$ (25)

###### Definition III.11

Let ${\mathcal{A}}$ and $\overline{{\mathcal{A}}}$ be two $n+1$ dimensional
hypercomplex algebras. ${\mathcal{A}}$ and $\overline{{\mathcal{A}}}$ are
called isomorphic, if there exists a bijective mapping
$\Psi:{\mathcal{A}}\rightarrow\overline{{\mathcal{A}}}$, satisfying

  * (i)

$\displaystyle\Psi(1)=1$ (26)

  * (ii)

$\displaystyle\Psi(ax+by)=a\Psi(x)+b\Psi(y),\quad
x,y\in{\mathcal{A}},a,b\in{\mathbb{R}};$ (27)

  * (iii)

$\displaystyle\Psi(x*y)=\Psi(x)*\Psi(y),\quad x,y\in{\mathcal{A}}.$ (28)

$\Psi$ is called an isomorphism.

A straightforward verification shows the following result immediately.

###### Proposition III.12

Assume

$\begin{array}[]{l}{\mathcal{A}}=\left\\{x_{0}+\mathop{\sum}\limits_{i=1}^{n}x_{i}{\bf
i}_{i}\;|\;x_{0},x_{1}\textsterling\textlnot\cdots,x_{n}\in{\mathbb{R}}\right\\}\\\
\overline{{\mathcal{A}}}=\left\\{\bar{x}_{0}+\mathop{\sum}\limits_{i=1}^{n}\bar{x}_{i}{\bf
j}_{i}\;|\;\bar{x}_{0},\bar{x}_{1}\textsterling\textlnot\cdots,\bar{x}_{n}\in{\mathbb{R}}\right\\}.\\\
\end{array}$

${\mathcal{A}}$ and $\overline{{\mathcal{A}}}$ are isomorphic, if and only if,
there is a non-singular matrix $T\in{\mathbb{R}}_{(n+1)\times(n+1)}$ of the
form (24), such that (25) holds true.

###### Proposition III.13

Assume
${\mathcal{A}},~{}\overline{{\mathcal{A}}}\in\mbox{\boldmath$H$}_{n+1}$, with
their PSMs as $P_{{\mathcal{A}}}$ and $P_{\overline{{\mathcal{A}}}}$
respectively. ${\mathcal{A}}$ and $\overline{{\mathcal{A}}}$ are isomorphic,
if and only if, there exists a non-singular matrix $T$ as in (24) such that

$\displaystyle
P_{\overline{{\mathcal{A}}}}=T^{-1}P_{{\mathcal{A}}}\left(T\otimes T\right).$
(29)

###### Proof:

(Necessary) Let $T$ be constructed as is (24), such that

$\bar{x}=T^{-1}x.$

Then we have

$\displaystyle
P_{{\mathcal{A}}}xy=TP_{\overline{\mathcal{A}}}\bar{x}\bar{y},\quad
x,y\in{\mathcal{A}}.$ (30)

The right hand side (RHS) of (30) becomes

$\begin{array}[]{ccl}RHS_{(\ref{3.3.8})}&=&=TP_{\overline{\mathcal{A}}}T^{-1}xT^{-1}y\\\
{}\hfil&=&TP_{\overline{\mathcal{A}}}T^{-1}\left(I_{n+1}\otimes
T^{-1}\right)xy.\end{array}$

Since $x,y$ are arbitrary, we have

$P_{{\mathcal{A}}}=TP_{\overline{\mathcal{A}}}T^{-1}\left(I_{n+1}\otimes
T^{-1}\right).$

Hence,

$\begin{array}[]{ccl}P_{\overline{\mathcal{A}}}&=&T^{-1}P_{{\mathcal{A}}}\left(I_{n+1}\otimes
T\right)T\\\ {}\hfil&=&T^{-1}P_{{\mathcal{A}}}\left(T\otimes T\right)\\\
\end{array}$

(Sufficiency) If (30) holds true, it is easy to verify that

$\bar{x}=T^{-1}x$

is an isomorphism.

∎

##  IV Lower Dimensional PHAs

This section considers some examples of various dimensional algebras.

###  IV-A Structure of ${\mathcal{A}}\in\mbox{\boldmath$H$}_{2}$

Consider ${\mathcal{A}}\in\mbox{\boldmath$H$}_{2}$. According to
PropositionIII.3, its PSM is

$\displaystyle P_{{\mathcal{A}}}=\begin{bmatrix}1&0&0&\alpha\\\
0&1&1&\beta\end{bmatrix}$ (31)

Consider a coordinate change

$T=\begin{bmatrix}1&s\\\ 0&t\end{bmatrix},\quad t\neq 0.$

Using formula (29), we have

$\displaystyle\begin{array}[]{ccl}P_{\overline{\mathcal{A}}}&=&T^{-1}P_{{\mathcal{A}}}\left(T\otimes
T\right)\\\ {}\hfil&=&\begin{bmatrix}1&0&0&\alpha t^{2}-s(s+t\beta)\\\
0&1&1&s+t\beta\\\ \end{bmatrix}\end{array}$ (34)

Now we may choose

$s=-t\beta,$

Then we have

$\displaystyle P_{\overline{\mathcal{A}}}=\begin{bmatrix}1&0&0&\alpha t^{2}\\\
0&1&1&0\\\ \end{bmatrix}$ (35)

We consider them case by case.

  * •

If $\alpha=0$, we have

$\displaystyle P_{\overline{\mathcal{A}}}=\begin{bmatrix}1&0&0&0\\\ 0&1&1&0\\\
\end{bmatrix}$ (36)

  * •

If $\alpha>0$, choosing $t=\frac{1}{\sqrt{|\alpha|}}$, then we have that

$\displaystyle P_{\overline{\mathcal{A}}}=\begin{bmatrix}1&0&0&1\\\ 0&1&1&0\\\
\end{bmatrix}.$ (37)

  * •

If $\alpha<0$, choosing $t=\frac{1}{\sqrt{|\alpha|}}$ yields

$\displaystyle P_{\overline{\mathcal{A}}}=\begin{bmatrix}1&0&0&-1\\\
0&1&1&0\\\ \end{bmatrix}.$ (38)

We conclude that up to isomorphism there are three
${\mathcal{A}}\in\mbox{\boldmath$H$}_{2}$, they are

  * •

set of dual numbers (${\mathcal{A}}_{D}$), which corresponds to (36);

  * •

set of hyperbolic numbers (${\mathcal{A}}_{H}$), which corresponds to (37);

  * •

set of complex numbers (${\mathbb{C}}$), which corresponds to (38).

Next, using (21), we can calculate their characteristic functions.

  * •

$\displaystyle\xi_{{\mathcal{A}}_{D}}=x_{0}^{2}.$ (39)

Then

$\displaystyle{\mathcal{Z}}_{{\mathcal{A}}_{D}}=\\{x_{0}+x_{1}{\bf
i}\in{\mathcal{A}}_{D}\;|\;x_{0}=0\\}.$ (40)

  * •

$\displaystyle\xi_{{\mathcal{A}}_{H}}=x_{0}^{2}-x_{1}^{2}.$ (41)

Then

$\displaystyle{\mathcal{Z}}_{{\mathcal{A}}_{D}}=\\{x_{0}+x_{1}{\bf
i}\in{\mathcal{A}}_{H}\;|\;x_{0}=\pm x_{1}\\}.$ (42)

  * •

$\displaystyle\xi_{{\mathbb{C}}}=x_{0}^{2}+x_{1}^{2};.$ (43)

Then

$\displaystyle{\mathcal{Z}}_{{\mathbb{C}}}=\\{0\\}.$ (44)

###### Remark IV.1

  * (i)

It is obvious that all ${\mathcal{A}}_{D}$, ${\mathcal{A}}_{H}$, and
${\mathbb{C}}$ are associative and commutative, that is they are all PHAs.

  * (ii)

They have minimum polynomials $x_{0}^{2}$, $x_{0}^{2}-x_{1}^{2}$, and
$x_{0}^{2}+x_{1}^{2}$ respectively. According to Galois theory, only the
minimum polynomial of ${\bf i}$ is irreducible, the extension is a field.
Hence, only ${\mathbb{C}}$ is a fields.

  * (iii)

It is easily seen that their zero sets are all zero measure set. This is
always true for all PHA. Because their zero set are zero set of algebraic
equations, which are called algebraic numbers. The set of algebraic numbers is
always zero measure set.

###  IV-B Structure of Triternions

###### Definition IV.2

An algebra ${\mathcal{A}}$ of dimension $3$ is called a triternion if
${\mathcal{A}}\in\mbox{\boldmath$H$}_{3}$.

It is easy to see that if ${\mathcal{A}}\in\mbox{\boldmath$H$}_{3}$ is
symmetric, then its PSM is

$\displaystyle P_{{\mathcal{A}}}=\begin{bmatrix}1&0&0&0&a&d&0&d&p\\\
0&1&0&1&b&e&0&e&q\\\ 0&0&1&0&c&f&1&f&r\\\ \end{bmatrix}$ (45)

Next, we consider when ${\mathcal{A}}$ is associative. According to Theorem
II.7, the necessary and sufficient condition is

$\displaystyle P^{2}_{{\mathcal{A}}}=P_{{\mathcal{A}}}\left(I_{3}\otimes
P_{{\mathcal{A}}}\right).$ (46)

Denote $I=I_{3}$,

$A=\begin{bmatrix}0&a&d\\\ 1&b&e\\\ 0&c&f\end{bmatrix},\quad
B=\begin{bmatrix}0&d&p\\\ 0&e&q\\\ 1&f&r\end{bmatrix}.$

A direct computation shows that

$\displaystyle\begin{array}[]{l}\mbox{LHS of
(\ref{4.2.2})}=(I,A,B,A,aI+bA+cB,\\\ dI+eA+fB,B,dI+eA+fB,pI+qA+rB),\\\
\mbox{RHS of (\ref{4.2.2})}=(I,A,B,A,A^{2},AB,B,BA,B^{2}).\end{array}$ (50)

Then we have the following result:

###### Theorem IV.3

${\mathcal{A}}\in\mbox{\boldmath$H$}_{3}$, if and only if, $P_{{\mathcal{A}}}$
has the form of (45) with parameters satisfying

$\displaystyle\begin{array}[]{l}a=ce+f^{2}-bf-cr,\\\ d=cq-ef,\\\ p=e^{2}+fq-
bq-er.\\\ \end{array}$ (54)

###### Proof:

(Necessity) Comparing both sides of (LABEL:5.2), (LABEL:5.3) shows that a
necessary condition for (46) holds true is (refer to the 6th and 8th blocks of
both sides)

$\displaystyle AB=BA.$ (55)

Then it is easy to verify that (54) provides necessary and sufficient
condition for (55) to be true.

(Sufficiency) A careful computation shows as long as (54) holds, the RHS of
(46) and the LHS of (46), shown in (50), are equal.

∎

###### Remark IV.4

Theorem IV.3) provides an easy way to construct
${\mathcal{A}}\in\mbox{\boldmath$H$}_{3}$. In fact, the parameters
$b,c,e,f,q,r$ can be assigned freely, then $a,d,p$ can be obtained by (54). It
is easy to see that there are uncountably many algebras of dimension 3, which
are commutative and associative.

Next, we give a numerical example.

###### Example IV.5

Construct ${\mathcal{A}}\in\mbox{\boldmath$H$}_{3}$ by setting $b=c=f=q=r=0$
and $e=1$. Then we have $d=a=0$ and $p=1$. The PSM of ${\mathcal{A}}$ is

$\displaystyle P_{{\mathcal{A}}}=\begin{bmatrix}1&0&0&0&0&0&0&0&1\\\
0&1&0&1&0&1&0&1&0\\\ 0&0&1&0&0&0&1&0&0\\\ \end{bmatrix}.$ (56)

In fact, when $x\in{\mathcal{A}}$ is expressed into standard form as

$x=x_{0}+x_{1}{\bf i}_{1}+x_{2}{\bf i}_{2},\quad
x_{0},x_{1},x_{2}\in{\mathbb{R}},$

then we have

$\begin{array}[]{l}{\bf i}_{1}^{2}=0;\quad{\bf i}_{2}^{2}=1,\\\ {\bf
i}_{1}*{\bf i}_{2}={\bf i}_{2}*{\bf i}_{1}={\bf i}_{1}.\end{array}$

Then it is easy to calculate that

$\displaystyle\xi_{{\mathcal{A}}}=(x_{0}-x_{2})(x_{0}+x_{2})^{2}.$ (57)

Hence,

$\displaystyle{\mathcal{Z}}_{{\mathcal{A}}}=\\{(x_{0},x_{1},x_{2})\in{\mathbb{R}}^{3}\;|\;x_{0}=\pm
x_{2}\\}.$ (58)

###  IV-C Structure of Perfect Quaternions

This section considers some some algebras in $\mbox{\boldmath$H$}_{4}$. It
seems not easy to provide a general description for algebras in
$\mbox{\boldmath$H$}_{4}$. The principle argument is similar to triternions.
We give some simple examples.

###### Example IV.6

Consider an ${\mathcal{A}}\in\mbox{\boldmath$H$}_{4}$. Assume

${\mathcal{A}}=\left\\{p_{0}+p_{1}{\bf i}_{1}+p_{2}{\bf i}_{2}+p_{3}{\bf
i}_{3}\;|\;p_{0},p_{1},p_{2},p_{3}\in{\mathbb{R}}\right\\},$

satisfying

$\begin{array}[]{ll}{\bf i}_{1}^{2},{\bf i}_{2}^{2},{\bf
i}_{3}^{2}\in\\{-1,0,1\\},&{\bf i}_{1}*{\bf i}_{2}={\bf i}_{2}*{\bf
i}_{1}=\pm{\bf i}_{3},\\\ {\bf i}_{2}*{\bf i}_{3}={\bf i}_{3}*{\bf
i}_{2}=\pm{\bf i}_{1},&{\bf i}_{3}*{\bf i}_{1}={\bf i}_{1}*{\bf i}_{3}=\pm{\bf
i}_{2}.\\\ \end{array}$

To save space, we denote

$P_{{\mathcal{A}}_{i}}=[I_{4},Q_{i}].$

Using MATLAB for an exhausting searching, we got eight algebras as follows:

  * •

$Q_{1}=\left[\begin{array}[]{cccccccccccc}0&-1&0&0&0&0&-1&0&0&0&0&1\\\
1&0&0&0&0&0&0&1&0&0&1&0\\\ 0&0&0&1&1&0&0&0&0&1&0&0\\\
0&0&-1&0&0&-1&0&0&1&0&0&0\end{array}\right]$

  * •

$Q_{2}=\left[\begin{array}[]{cccccccccccc}0&-1&0&0&0&0&-1&0&0&0&0&1\\\
1&0&0&0&0&0&0&-1&0&0&-1&0\\\ 0&0&0&-1&1&0&0&0&0&-1&0&0\\\
0&0&1&0&0&1&0&0&1&0&0&0\end{array}\right]$

  * •

$Q_{3}=\left[\begin{array}[]{cccccccccccc}0&-1&0&0&0&0&1&0&0&0&0&-1\\\
1&0&0&0&0&0&0&-1&0&0&-1&0\\\ 0&0&0&1&1&0&0&0&0&1&0&0\\\
0&0&-1&0&0&-1&0&0&1&0&0&0\end{array}\right]$

  * •

$Q_{4}=\left[\begin{array}[]{cccccccccccc}0&-1&0&0&0&0&1&0&0&0&0&-1\\\
1&0&0&0&0&0&0&1&0&0&1&0\\\ 0&0&0&-1&1&0&0&0&0&-1&0&0\\\
0&0&1&0&0&1&0&0&1&0&0&0\end{array}\right]$

  * •

$Q_{5}=\left[\begin{array}[]{cccccccccccc}0&1&0&0&0&0&-1&0&0&0&0&-1\\\
1&0&0&0&0&0&0&1&0&0&1&0\\\ 0&0&0&-1&1&0&0&0&0&-1&0&0\\\
0&0&-1&0&0&-1&0&0&1&0&0&0\end{array}\right]$

  * •

$Q_{6}=\left[\begin{array}[]{cccccccccccc}0&1&0&0&0&0&-1&0&0&0&0&-1\\\
1&0&0&0&0&0&0&-1&0&0&-1&0\\\ 0&0&0&1&1&0&0&0&0&1&0&0\\\
0&0&1&0&0&1&0&0&1&0&0&0\end{array}\right]$

  * •

$Q_{7}=\left[\begin{array}[]{cccccccccccc}0&1&0&0&0&0&1&0&0&0&0&1\\\
1&0&0&0&0&0&0&-1&0&0&-1&0\\\ 0&0&0&-1&1&0&0&0&0&-1&0&0\\\
0&0&-1&0&0&-1&0&0&1&0&0&0\end{array}\right]$

  * •

$Q_{8}=\left[\begin{array}[]{cccccccccccc}0&1&0&0&0&0&1&0&0&0&0&1\\\
1&0&0&0&0&0&0&1&0&0&1&0\\\ 0&0&0&1&1&0&0&0&0&1&0&0\\\
0&0&1&0&0&1&0&0&1&0&0&0\end{array}\right]$

Next, choose some ${\mathcal{A}}\in\mbox{\boldmath$H$}_{4}$ for further study.

###### Example IV.7

Recall Example IV.6).

  * (i)

Consider ${\mathcal{A}}_{3}$:

It is easy to calculate that

$\displaystyle\begin{array}[]{ccl}\xi_{{\mathcal{A}}_{3}}&=&\det(P_{{\mathcal{A}}_{3}}x)\\\
{}\hfil&=&(x_{0}^{2}-x_{2}^{2})^{2}+(x_{1}^{2}-x_{3}^{2})^{2}\\\
{}{}\hfil&{}\hfil&+2(x_{0}x_{1}+x_{2}x_{3})^{2}+2(x_{0}x_{3}+x_{1}x_{2})^{2}.\end{array}$
(62)

It follows that

$\displaystyle\begin{array}[]{l}{\mathcal{Z}}_{{\mathcal{A}}_{3}}=\left\\{(x_{0},x_{1},x_{2},x_{3})^{T}\in{\mathbb{R}}^{4}\;|\;\right.\\\
\left.(x_{0}=x_{2})\cap(x_{1}=-x_{3})~{}\mbox{or}~{}(x_{0}=-x_{2})\cap(x_{1}=x_{3})\right\\}.\end{array}$
(65)

  * (ii)

Consider ${\mathcal{A}}_{8}$:

It is easy to calculate that

$\displaystyle\begin{array}[]{ccl}\xi_{{\mathcal{A}}_{8}}&=&\det(P_{{\mathcal{A}}_{8}}x)\\\
{}\hfil&=&x_{0}^{4}+x_{1}^{4}+x_{2}^{4}+x_{3}^{4}\\\
{}{}\hfil&{}\hfil&-2(x^{2}_{0}x^{2}_{1}+x^{2}_{0}x_{2}^{2}+x^{2}_{0}x^{3}_{3}+x^{2}_{1}x^{2}\\\
{}\hfil&{}\hfil&+x^{2}_{1}x_{3}^{2}+x_{2}^{2}x_{3}^{2})+8x_{0}x_{1}x_{2}x_{3}.\end{array}$
(70)

It follows that

$\displaystyle\begin{array}[]{l}{\mathcal{Z}}_{{\mathcal{A}}_{8}}=\left\\{(x_{0},x_{1},x_{2},x_{3})^{T}\in{\mathbb{R}}^{4}\;|\;\right.\\\
\left.\xi_{{\mathcal{A}}_{8}}(x_{0},x_{1},x_{2},x_{3})=0\right\\}.\end{array}$
(73)

###  IV-D Some Other Examples

To see there are also ${\mathcal{A}}\in\mbox{\boldmath$H$}_{n}$, for $n>4$,
such examples are presented as follows. First example is a set of simplest
PHAs, which are called trivial PHAs.

###### Example IV.8

Define an $n+1$ dimensional algebra ${\mathcal{A}}_{n+1}^{0}$ as follows: Let
${\bf i}_{k}$, $k=1,2,\cdots,n$ be its hyperimaginary units. Set

${\bf i}_{s}*{\bf i}_{t}=0,\quad s,t=1,2,\cdots,n.$

Then it is easy to verify that
${\mathcal{A}}_{n+1}^{0}\in\mbox{\boldmath$H$}_{n+1}$. Moreover, its PSM,
$P_{{|calA}_{n+1}^{0}}$ can be determined by the following:

$\displaystyle\operatorname{Col}_{i}\left(P_{{\mathcal{A}}_{n+1}^{0}}\right)=\begin{cases}\delta_{n+1}^{i},\quad
i=1,2,\cdots,n+1;\\\ \delta_{n+1}^{r+1},\quad i=r(n+1)+1,\;r=1,2,\cdots,n,\\\
0,\quad\mbox{Otherwise}.\end{cases}$ (74)

Its characteristic function is

$\displaystyle\xi_{{\mathcal{A}}_{D}^{n}}=x_{0}^{n+1}.$ (75)

Hence,

$\displaystyle{\mathcal{Z}}_{{\mathcal{A}}_{D}^{n}}=\\{x_{0}+x_{1}{\bf
i}_{1}+\cdots+x_{n}{\bf i}_{n}\;|\;x_{0}=0\\}.$ (76)

If $x\in{\mathcal{Z}}^{c}_{{\mathcal{A}}_{D}^{n}}$, say

$x=x_{0}+x_{1}{\bf i}_{1}+\cdots+x_{n}{\bf i}_{n},\quad x_{0}\neq 0,$

then

$x^{-1}=\frac{1}{x_{0}}-\mathop{\sum}\limits_{i=1}^{n}\frac{x_{i}}{x_{0}^{2}}{\bf
i}_{i}.$

Next, we give an example for $n=5$.

###### Example IV.9

Consider a hypercomplex algebra ${\mathcal{A}}$, which has its PSM as

$\displaystyle\begin{array}[]{ccl}P_{{\mathcal{A}}}&:=&\delta_{5}[1,2,3,4,5,2,0,0,3,0,3,0,\\\
&&~{}~{}~{}0,0,0,4,3,0,0,0,5,0,0,0,0],\\\ \end{array}$ (79)

where $\delta_{5}^{0}={\bf 0}_{5}$.

A straightforward computation shows that ${\mathcal{A}}$ is commutative and
associative, hence ${\mathcal{A}}\in\mbox{\boldmath$H$}_{5}$. Then it is easy
to calculate that

$\displaystyle\xi_{{\mathcal{A}}}(x)=x_{0}^{3}(x_{0}^{2}-x_{1}x_{3}).$ (80)

So its zero set is

$\displaystyle{\mathcal{Z}}_{{\mathcal{A}}}=\\{(x_{0},x_{1},x_{2},x_{3},x_{4})^{T}\in{\mathbb{R}}^{5}\;|\;x_{0}=0,~{}\mbox{or}~{}x_{0}^{2}=x_{1}x_{3}\\}.$
(81)

##  V Conclusion

In this paper the perfect hypercomplex algebra is considered. Using STP,
necessary and sufficient conditions on the structure matrix of an algebra to
be a PHA is proposed. Based on the matrix expression of homomorphisms between
algebras, certain lower dimensional PHAs are classified up to isomorphism.
Their characteristic functions and zero sets are discussed.

## References

  * [1] V. Abramov, Noncommutative Galois extension and graded q-differential algebra, Adv. in Appl. Clifford Alg., Vol. 26, 1-11, 2016.
  * [2] S. Alam, Comparative study of mixed product and quaternion product, Adv. in Appl. Clifford Alg., Vol. 12, No. 2, 189-194, 2002.
  * [3] D. Cheng, H. Qi, Z. Li, Analysis and Control of Boolean Networks - A Semi-tensor Product Approach, Springer, London, 2011.
  * [4] D. Cheng, H. Qi, Y. Zhao, An Introduction to Semi-tensor Product of Matrices and Its Applications, World Scientific, Singapore, 2012.
  * [5] D. Cheng, Y. Li, J. Feng, J. Zhao, On numerical/non-numerical algebra via semi-tensor product method, Math. Modelling and Control, Vol. 1, No. 1, 1-11, 2021.
  * [6] S. Fu, D. Cheng, J. Feng, J. Zhao, Matrix expression of finite Boolean-type algebras, Applied Math. Comp., Vol. 395, (2021) 125880, 2021.
  * [7] T.W. Hungerford, Algebra, Springer-Verlag, New York, 1974.
  * [8] W.L. Li, Lecture on History of Mathematics, Higher Edication Press, Beijing, 1999 (in Chinese).
  * [9] F.Z. Castro, M.E.Valle, A broad class of discrete-time hypercomplex-valued Hopfield neural networks, arXiv: 1902.05478v3 [cs.LG] 31 Oct, 2019, 2019.
  * [10] S. Pei, J. Chang, J. Ding, Commutative reduced biquaternions and their fourier transform for signal and image processing applications, IEEE Trans. Signal Proc., Vol. 52, No. 7, 2012-2031, 2004.
  * [11] A. Shenitzer, I. Kantor, A. Solodovnikov, Hypercomplex Numbers: An Elementary Introduction to Algebras, Springer-Verlag, New York, 1989.