# Analyzing the group sparsity based on the rank minimization methods

###### Abstract

Sparse coding has achieved a great success in various image processing
studies. However, there is not any benchmark to measure the sparsity of image
patch/group because sparse discriminant conditions cannot keep unchanged. This
paper analyzes the sparsity of group based on the strategy of the rank
minimization. Firstly, an adaptive dictionary for each group is designed.
Then, we prove that group-based sparse coding is equivalent to the rank
minimization problem, and thus the sparse coefficient of each group are
measured by estimating the singular values of each group. Based on that
measurement, the weighted Schatten $p$-norm minimization (WSNM) has been found
to be the closest solution to the real singular values of each group. Thus,
WSNM can be equivalently transformed into a non-convex $\ell_{p}$-norm
minimization problem in group-based sparse coding. To make the proposed scheme
tractable and robust, the alternating direction method of multipliers (ADMM)
is used to solve the $\ell_{p}$-norm minimization problem. Experimental
results on two applications: image inpainting and image compressive sensing
(CS) recovery have shown that the proposed scheme outperforms many state-of-
the-art methods.

Index Terms—  group sparsity, rank minimization, the weighted schatten
$p$-norm, $\ell_{p}$-norm, adaptive dictionary.

##  1 Introduction

Traditional patch-based sparse coding assumes that each patch of an image can
be precisely modeled as a sparse linear combination of basic elements. It has
been successfully used in various image processing applications [1, 2, 3, 4].
However, patch-based sparse coding model of natural images usually suffers
from some limits, such as dictionary learning with great computational
complexity, neglecting the relationship between similar patches.

Instead of using patch as the basic unit of sparse coding, group-based sparse
coding can offer a powerful mechanism of combining local sparsity and nonlocal
self-similarity of images simultaneously in a unified framework [3, 6]. To be
concrete, an image X with size $N$ is divided into $n$ overlapped patches of
size $\sqrt{d}\times\sqrt{d}$, and each patch is denoted by the vector
${\textbf{\emph{x}}}_{i}\in\Re^{d},i=1,2,...,n$. Then for each patch
${\textbf{\emph{x}}}_{i}$, its $k$ similar patches are selected from a
$I\times I$ sized search window to form a set ${\textbf{\emph{S}}}_{i}$. After
this, all the patches in ${\textbf{\emph{S}}}_{i}$ are stacked into a matrix
${\textbf{\emph{X}}}_{i}\in\Re^{d\times k}$, i.e.,
${\textbf{\emph{X}}}_{i}=\\{{\textbf{\emph{x}}}_{i,1},{\textbf{\emph{x}}}_{i,2},...,{\textbf{\emph{x}}}_{i,k}\\}$.
The matrix ${\textbf{\emph{X}}}_{i}$ consists of all the patches with similar
structures is called a group, where ${\textbf{\emph{x}}}_{i,k}$ denotes the
$k$-th similar patch of the $i$-th group. Similar to patch-based sparse coding
[1], given a dictionary ${\textbf{\emph{D}}}_{i}$, each group
${\textbf{\emph{X}}}_{i}$ can be sparsely represented as
${\boldsymbol{\alpha}}_{i}={\textbf{\emph{D}}}_{i}^{-1}{\textbf{\emph{X}}}_{i}$
and solved by the following $\ell_{0}$-norm minimization problem,

${\boldsymbol{\alpha}}_{i}=\arg\min_{{\boldsymbol{\alpha}}_{i}}\\{\frac{1}{2}||{\textbf{\emph{X}}}_{i}-{\textbf{\emph{D}}}_{i}{\boldsymbol{\alpha}}_{i}||_{F}^{2}+\lambda||{\boldsymbol{\alpha}}_{i}||_{0}\\}$
(1)

where $\lambda$ is the regularization parameter, $||*||_{F}^{2}$ denotes the
Frobenius norm, and $||*||_{0}$ is $\ell_{0}$-norm, counting the non-zero
entries of ${\boldsymbol{\alpha}}_{i}$.

However, since $||*||_{0}$ norm minimization is a difficult combinatorial
optimization problem, solving Eq. (1) is NP-hard. For this reason, it is often
replaced by the $\ell_{1}$-norm or the reweighted $\ell_{1}$-norm to make the
optimization problem easy [5]. Nonetheless, the solution of these norm
minimizations is only the estimation of the real sparsity solution under
certain conditions. For instance, Candès $\emph{et al}.$ [7] proposed that
solving $\ell_{1}$-norm optimization problem can recover a $K$-sparse signal
$\textbf{\emph{x}}\in\Re^{N}$ from $M=O(Klog(N/K))$ random measurements in
compressive sensing (CS). However, the $\ell_{1}$-norm minimization cannot
still obtain the real sparsity solution, one important reason is nobody can
guarantee the invariance of sparse discriminant conditions. In other words,
there is not any benchmark to measure the sparsity of a signal.

With the above consideration, we analyze the group sparsity from the point of
the rank minimization. To the best of our knowledge, few works have exploited
the rank minimization methods to analyze the sparsity of image groups. The
contribution of this paper is as follows. First, an adaptive dictionary for
each group is designed with a low computational complexity, rather than
dictionary learning from natural images. Second, based on this dictionary
learning scheme, we prove the equivalence of group-based sparse coding and the
rank minimization problem, and thus the sparse coefficient of each group are
measured by calculating the singular values of each group. Thus, we have a
benchmark to measure the sparsity of each group because the singular values of
the original image group can be easily computed by SVD operator. Third, we
exploit four nuclear norms (i.e., standard nuclear norm [8], the weighted
nuclear norm [9], Schatten $p$-norm [10] and the weighted Schatten $p$-norm
[11]) to analyze the sparsity of each group and the solution of the weighted
Schatten $p$-norm minimization (WSNM) is the nearest to real singular values
of each group. Therefore, WSNM is equivalently turned into a non-convex
$\ell_{p}$-norm minimization problem in group-based sparse coding. To make the
proposed scheme tractable and robust, we exploit the alternating direction
method of multipliers (ADMM) to solve the non-convex $\ell_{p}$-norm
minimization problem. Experimental results on two low-level vision tasks,
i.e., image inpainting and image compressive sensing (CS) recovery have
demonstrated that the proposed scheme outperforms many state-of-the-art
schemes.

##  2 Background

###  2.1 Rank minimization method

The main goal of low rank matrix approximation (LRMA) is to recover the
underlying low rank structure from its degraded/corrupted observed version. In
general, methods of LRMA can be classified into two categories: the low rank
matrix factorization (LRMF) methods [12, 13] and the rank minimization methods
[8, 9, 10, 11]. In this work we focus on the latter category. More
specifically, given an input matrix Y, the rank minimization methods aim to
find a low rank matrix X, which is as close to Y as possible under $F$-norm
data fidelity and one nuclear norm,

$\hat{\textbf{\emph{X}}}={\arg\min}_{\textbf{\emph{X}}}||\textbf{\emph{Y}}-\textbf{\emph{X}}||_{F}^{2}+\lambda\textbf{\emph{R}}(\textbf{\emph{X}})$
(2)

where $\lambda$ is a trade-off parameter between the loss function and the low
rank regularization induced by one nuclear norm
$\textbf{\emph{R}}(\textbf{\emph{X}})$. We will briefly introduce several
nuclear norms including standard nuclear norm [8], the weighted nuclear norm
[9], Scappten $p$-norm [10] and the weighted Scappten $p$-norm [11] in the
next subsection.

###  2.2 Nuclear norms

In this subsection, we first introduce the weighted Schatten $p$-norm [11] of
a matrix $\textbf{\emph{X}}\in\Re^{m\times n}$, which is defined as

$||\textbf{\emph{X}}||_{\textbf{\emph{w}},S_{p}}=\left(\sum\nolimits_{i=1}^{min\\{m,n\\}}w_{i}\sigma_{i}^{p}\right)^{\frac{1}{p}}$
(3)

where $0<p\leq 1$, and $\sigma_{i}$ is the $i$-th singular value of X.
$\textbf{\emph{w}}=[w_{1},...,w_{min\\{m,n\\}}]$ and $w_{i}\geq 0$ is a non-
negative weight assigned to $\sigma_{i}$. Then the weighted Schatten $p$-norm
of X with power $p$ is

$||\textbf{\emph{X}}||_{\textbf{\emph{w}},S_{p}}^{p}=\left(\sum\nolimits_{i=1}^{min\\{m,n\\}}w_{i}\sigma_{i}^{p}\right)=Tr(\textbf{\emph{W}}{\boldsymbol{\Delta}}^{p})$
(4)

where W and ${\boldsymbol{\Delta}}$ are diagonal matrices whose diagonal
entries are composed of $w_{i}$ and $\sigma_{i}$, respectively.

The Schatten $p$-norm [10] of a matrix X can be represented by setting
$\textbf{\emph{w}}=[1,1,...,1]$ in Eq. (3),

$||\textbf{\emph{X}}||_{S_{p}}=\left(\sum\nolimits_{i=1}^{min\\{m,n\\}}\sigma_{i}^{p}\right)^{\frac{1}{p}}=\left(Tr(({\textbf{\emph{X}}}^{T}{\textbf{\emph{X}}})^{\frac{p}{2}})\right)^{\frac{1}{p}}$
(5)

The weighted nuclear norm [9] of a matrix X can be represented by setting
$p$=1 in Eq. (3),

$||\textbf{\emph{X}}||_{\textbf{\emph{w},*}}=\left(\sum\nolimits_{i=1}^{min\\{m,n\\}}w_{i}\sigma_{i}\right)=Tr(\textbf{\emph{W}}{\boldsymbol{\Delta}})$
(6)

A widely used standard nuclear norm [8] of a matrix X can be represented by
setting $p$=1 and $\textbf{\emph{w}}=[1,1,...,1]$ in Eq. (3),

$||\textbf{\emph{X}}||_{*}=\sum\nolimits_{i=1}^{min\\{m,n\\}}\sigma_{i}=Tr(({\textbf{\emph{X}}}^{T}{\textbf{\emph{X}}})^{\frac{1}{2}})$
(7)

##  3 Analyzing the sparsity of group based on the rank minimization methods

Since the sparse discriminant conditions cannot keep unchanged, there is not
any benchmark to measure the sparsity of image group. Therefore, we analyze
the group sparsity from the point of the rank minimization. To this end, an
adaptive dictionary for each group is designed with a low computational
complexity, rather than dictionary learning from natural images. Based on this
dictionary learning scheme, we prove the equivalence of group-based sparse
coding and the rank minimization problem, i.e., the sparse coefficient of each
group are measured by calculating the singular values of each group.
Therefore, we possess a benchmark to measure the sparsity of each group by
rank minimization methods since the singular values of the original image
group can be easily obtained. In this way, we can achieve a clear visual
comparison effect to analyze the sparsity of each group based on the rank
minimization methods (See Fig. 1).

###  3.1 Adaptive dictionary learning

In this subsection, an adaptive dictionary learning method is designed, that
is, for each group ${\textbf{\emph{X}}}_{i}$, its adaptive dictionary can be
learned from its observation ${\textbf{\emph{Y}}}_{i}\in\Re^{d\times k}$.

More specifically, we apply the singular value decomposition (SVD) to
${\textbf{\emph{Y}}}_{i}$,

${\textbf{\emph{Y}}}_{i}={\textbf{\emph{U}}}_{i}{\boldsymbol{\Sigma}}_{i}{\textbf{\emph{V}}}_{i}^{T}=\sum\nolimits_{j=1}^{m}\boldsymbol{\sigma}_{i,j}{\textbf{\emph{u}}}_{i,j}{\textbf{\emph{v}}}_{i,j}^{T}$
(8)

where
$\boldsymbol{\mu}_{i}=[\boldsymbol{\sigma}_{i,1},\boldsymbol{\sigma}_{i,2},...,\boldsymbol{\sigma}_{i,m}]$,
$m={\rm min}(d,k)$, ${\boldsymbol{\Sigma}}_{i}={\rm
diag}(\boldsymbol{\mu}_{i})$ is a diagonal matrix whose non-zero elements are
represented by $\boldsymbol{\mu}_{i}$, and
${\textbf{\emph{u}}}_{i,j},{\textbf{\emph{v}}}_{i,j}$ are the columns of
${\textbf{\emph{U}}}_{i}$ and ${\textbf{\emph{V}}}_{i}$, respectively.

Moreover, we define each dictionary atom $\textbf{\emph{d}}_{i,j}$ of the
adaptive dictionary $\textbf{\emph{D}}_{i}$ for each group
$\textbf{\emph{Y}}_{i}$ as follows:

$\textbf{\emph{d}}_{i,j}={\textbf{\emph{u}}}_{i,j}{\textbf{\emph{v}}}_{i,j}^{T},\
\ \ j=1,2,...,m$ (9)

Finally, by learning an adaptive dictionary
$\textbf{\emph{D}}_{i}=[\textbf{\emph{d}}_{i,1},\textbf{\emph{d}}_{i,2},...,\textbf{\emph{d}}_{i,m}]$
from each group ${\textbf{\emph{Y}}}_{i}$. The proposed dictionary learning
method is efficient due to the fact that it only requires one SVD operator for
each group.

###  3.2 Prove the equivalence of group-based sparse coding and the rank
minimization problem

To prove that the group-based sparse coding is equivalent to the rank
minimization problem, we firstly give following two lemmas.

Lemma 1 The minimization problem

${\textbf{\emph{x}}}=\arg\min_{\textbf{\emph{x}}}\frac{1}{2}||{\textbf{\emph{x}}}-{\textbf{\emph{a}}}||_{2}^{2}+\tau.||{\textbf{\emph{x}}}||_{1}$
(10)

has a closed form, which can be expressed as

$\hat{\textbf{\emph{x}}}={\rm soft}({\textbf{\emph{a}}},\tau)={\rm
sgn}({\textbf{\emph{a}}},\tau).{\rm max}(abs({\textbf{\emph{a}}})-\tau,0)$
(11)

_Proof:_ see [14].

Consider the SVD of a matrix $\textbf{\emph{P}}\in\Re^{n_{1}\times n_{2}}$ of
rank $r$

$\textbf{\emph{P}}=\textbf{\emph{U}}\boldsymbol{\Sigma}\textbf{\emph{V}}^{T},\boldsymbol{\Sigma}={\rm
diag}(\\{\sigma_{i}\\}_{1\leq i\leq r})$ (12)

where $\textbf{\emph{U}}\in\Re^{n_{1}\times r}$ and
$\textbf{\emph{V}}\in\Re^{n_{2}\times r}$ are orthogonal matrices,
respectively. $\sigma_{i}$ is the $i$-th singular value of P. For each
$\tau\geq 0$, the soft-thresholding operator $\mathcal{D}_{\tau}$ is defined
as

$\mathcal{D}_{\tau}(\textbf{\emph{P}})=\textbf{\emph{U}}\mathcal{D}_{\tau}(\boldsymbol{\Sigma})\textbf{\emph{V}}^{T},\
\ \ \mathcal{D}_{\tau}(\boldsymbol{\Sigma})={\rm soft}(\sigma_{i},\tau)$ (13)

Lemma 2 For each $\tau\geq 0$, and $\textbf{\emph{Q}}\in\Re^{n_{1}\times
n_{2}}$ ,the singular value shrinkage operator Eq. (13) satisfies

$\mathcal{D}_{\tau}(\textbf{\emph{Q}})=\arg\min_{\textbf{\emph{P}}}\\{\frac{1}{2}||{\textbf{\emph{P}}}-{\textbf{\emph{Q}}}||_{F}^{2}+\tau||{\textbf{\emph{P}}}||_{*}\\}$
(14)

_Proof:_ see Appendix.

Now, the classical $\ell_{1}$-norm group-based sparse coding problem can be
represented as

${\boldsymbol{\alpha}}_{i}=\arg\min\nolimits_{{\boldsymbol{\alpha}}_{i}}\\{||{\textbf{\emph{Y}}}_{i}-{\textbf{\emph{D}}}_{i}{\boldsymbol{\alpha}}_{i}||_{F}^{2}+\lambda||{\boldsymbol{\alpha}}_{i}||_{1}\\}$
(15)

According to the above design of adaptive dictionary
${\textbf{\emph{D}}}_{i}$, we have the following conclusion.

Theorem 1

$||{\textbf{\emph{Y}}}_{i}-{\textbf{\emph{X}}}_{i}||_{F}^{2}=||\boldsymbol{\mu}_{i}-\boldsymbol{\alpha}_{i}||_{2}^{2}$
(16)

where ${\textbf{\emph{Y}}}_{i}={\textbf{\emph{D}}}_{i}\boldsymbol{\mu}_{i}$
and ${\textbf{\emph{X}}}_{i}={\textbf{\emph{D}}}_{i}\boldsymbol{\alpha}_{i}$.

_Proof:_ see Appendix.

Theorem 2

The equivalence of the group-based sparse coding and the rank minimization
problem is satisfied under the adaptive dictionary ${\textbf{\emph{D}}}_{i}$.

_Proof:_ see Appendix.

It can be similarly proven that the reweighted $\ell_{1}$-norm and
$\ell_{p}$-norm minimization are equivalent to the weighted nuclear norm
minimization (WNNM) [10] and the weighted Schatten $p$-norm minimization
(WSNM) [11], respectively.

Note that the main difference between sparse coding and the rank minimization
problem is that sparse coding has a dictionary learning operator and the rank
minimization problem does not involve.

###  3.3 Analyzing the sparsity of group based on the nuclear norms
minimization

Based on _Theorem 2_ , the group-based sparse coding can be turned into the
rank minimization problem. Now, four nuclear norms are used to constrain Eq.
(2) to analyze the sparsity of each group, i.e., nuclear norm minimization
(NNM) [8], the weighted nuclear norm minimization (WNNM) [9], Schatten
$p$-norm minimization (SNM) [10] and the weighted Schatten $p$-norm
minimization (WSNM) [11]. In these experiments, a gray image _Barbara_ is used
as an example in the context of image inpainting, where 80% pixels are damaged
in Fig. 1(b). We generate two groups based on 1# position and 2# position
which are shown in Fig. 1(a). As shown in Fig. 1(c) and Fig. 1(d), it can be
seen that the singular values of WSNM result are the best approximation to the
ground-truth in comparison with other methods. Therefore, based on Theorem 2,
WSNM can be equivalently transformed into solving the non-convex
$\ell_{p}$-norm minimization to measure the sparsity in group-based sparse
coding.

Fig. 1: Analyzing the sparsity of each group based nuclear norms minimization.

##  4 Image restoration using group-based sparse coding with non-convex
$\ell_{p}$-norm minimization

In this section, we verify the proposed scheme in the application of image
restoration (IR). IR aims to reconstruct a high quality image X from its
degraded observation Y,

$\textbf{\emph{Y}}=\textbf{\emph{H}}\textbf{\emph{X}}+\textbf{\emph{N}}$ (17)

where H is the degraded operator and N is usually assumed to be additive white
Gaussian noise. In this paper, we will focus on image inpainting and image
compressive sensing (CS) recovery.

In the scenario of IR, what we observed is the degraded image Y via Eq. (17),
and thus the goal is to employ the proposed scheme to recover the original
image X from Y by solving the following non-convex $\ell_{p}$-norm
minimization problem,

${{\boldsymbol{\alpha}}}=\arg\min\limits_{\boldsymbol{\alpha}}\frac{1}{2}||{\textbf{\emph{Y}}}-\textbf{\emph{H}}{\textbf{\emph{D}}}{{\boldsymbol{\alpha}}}||_{2}^{2}+\lambda||{\textbf{\emph{w}}}{{\boldsymbol{\alpha}}}||_{p}$
(18)

###  4.1 ADMM based for non-convex $\ell_{p}$-norm minimization

Solving the objective function of Eq. (18) is very difficult, since it is a
large scale non-convex optimization problem. To make the proposed scheme
tractable and robust, in this paper we present the alternating direction
method of multipliers (ADMM) [15] to solve Eq. (18). Specifically, we
introduce an auxiliary variable Z and Eq. (18) can be rewritten as

${{\boldsymbol{\alpha}}}=\arg\min\limits_{\textbf{\emph{Z}},\boldsymbol{\alpha}}\frac{1}{2}||{\textbf{\emph{Y}}}-\textbf{\emph{H}}{\textbf{\emph{Z}}}||_{2}^{2}+\lambda||{\textbf{\emph{w}}}{{\boldsymbol{\alpha}}}||_{p},\
\ s.t.\ \ \textbf{\emph{Z}}={\textbf{\emph{D}}}{{\boldsymbol{\alpha}}}$ (19)

By defining
$f(\textbf{\emph{Z}})=\frac{1}{2}||{\textbf{\emph{Y}}}-\textbf{\emph{H}}{\textbf{\emph{Z}}}||_{2}^{2}$,
and
$g(\boldsymbol{\alpha})=\lambda||{\textbf{\emph{w}}}{{\boldsymbol{\alpha}}}||_{p}$,
we have

${\textbf{\emph{Z}}}^{t+1}=\arg\min\limits_{\textbf{\emph{Z}}}\frac{1}{2}||\textbf{\emph{Y}}-\textbf{\emph{H}}{\textbf{\emph{Z}}}||_{2}^{2}+\frac{\rho}{2}||\textbf{\emph{Z}}-{{\textbf{\emph{D}}}{{\boldsymbol{\alpha}}}}^{t}-\textbf{\emph{C}}^{t}||_{2}^{2}$
(20)
${\boldsymbol{\alpha}}^{t+1}=\arg\min\limits_{\boldsymbol{\alpha}}\lambda||{\textbf{\emph{w}}}{{\boldsymbol{\alpha}}}||_{p}+\frac{\rho}{2}||\textbf{\emph{Z}}^{t+1}-{{\textbf{\emph{D}}}{{\boldsymbol{\alpha}}}}-\textbf{\emph{C}}^{t}||_{2}^{2}$
(21)

and

${\textbf{\emph{C}}}^{t+1}={\textbf{\emph{C}}}^{t}-({\textbf{\emph{Z}}}^{t+1}-{{\textbf{\emph{D}}}{{\boldsymbol{\alpha}}}}^{t+1})$
(22)

It can be seen that the minimization for Eq. (19) involves splitting two
minimization sub-problems, i.e., Z and ${{{\boldsymbol{\alpha}}}}$ sub-
problem. Next, we will show that there is an efficient solution to each sub-
problem. To avoid confusion, the subscribe $t$ may be omitted for conciseness.

####  4.1.1 Z sub-problem

Given ${{{\boldsymbol{\alpha}}}}$, the Z sub-problem denoted by Eq. (20)
becomes

$\min_{\textbf{\emph{Z}}}{\textbf{\emph{L}}}_{1}({{\textbf{\emph{Z}}}})=\min\limits_{\textbf{\emph{Z}}}\frac{1}{2}||\textbf{\emph{Y}}-\textbf{\emph{H}}{\textbf{\emph{Z}}}||_{2}^{2}+\frac{\rho}{2}||\textbf{\emph{Z}}-{{\textbf{\emph{D}}}{{\boldsymbol{\alpha}}}}-\textbf{\emph{C}}||_{2}^{2}$
(23)

Clearly, Eq. (23) has a closed-form solution and its solution can be expressed
as

$\hat{\textbf{\emph{Z}}}=({\textbf{\emph{H}}}^{T}{\textbf{\emph{H}}}+\rho{\textbf{\emph{I}}})^{-1}({\textbf{\emph{H}}}^{T}{\textbf{\emph{Y}}}+\rho({{\textbf{\emph{D}}}{{\boldsymbol{\alpha}}}}+\textbf{\emph{C}}))$
(24)

where I represents the identity matrix.

####  4.1.2 ${{{\boldsymbol{\alpha}}}}$ sub-problem

Given Z, similarity, according to Eq. (21), the ${{{\boldsymbol{\alpha}}}}$
sub-problem can be written as

$\min_{{{{\boldsymbol{\alpha}}}}}{\textbf{\emph{L}}}_{2}({{{{\boldsymbol{\alpha}}}}})=\min\limits_{{{\boldsymbol{\alpha}}}}\frac{1}{2}||{{\textbf{\emph{D}}}{{\boldsymbol{\alpha}}}}-\textbf{\emph{R}}||_{2}^{2}\\\
+\frac{\lambda}{\rho}||{\textbf{\emph{w}}}{{\boldsymbol{\alpha}}}||_{p}$ (25)

where $\textbf{\emph{R}}=\textbf{\emph{Z}}-\textbf{\emph{C}}$.

However, due to the complex structure of
$||{\textbf{\emph{w}}}{{\boldsymbol{\alpha}}}||_{p}$, it is difficult to solve
Eq. (25), Let
$\textbf{\emph{X}}={{\textbf{\emph{D}}}{{\boldsymbol{\alpha}}}}$, Eq. (25) can
be rewritten as

$\min_{{{{\boldsymbol{\alpha}}}}}{\textbf{\emph{L}}}_{2}({{{{\boldsymbol{\alpha}}}}})=\min\limits_{{{\boldsymbol{\alpha}}}}\frac{1}{2}||{{\textbf{\emph{X}}}}-\textbf{\emph{R}}||_{2}^{2}\\\
+\frac{\lambda}{\rho}||{\textbf{\emph{w}}}{{\boldsymbol{\alpha}}}||_{p}$ (26)

To enable a tractable solution of Eq. (26), in this paper, a general
assumption is made, with which even a closed form can be achieved.
Specifically, R can be regarded as some type of noisy observation of X, and
then the assumption is made that each element of
$\textbf{\emph{E}}=\textbf{\emph{X}}-\textbf{\emph{R}}$ follows an independent
zero-mean distribution with variance ${\sigma}^{2}$. The following conclusion
can be proved by this assumption.

Theorem 3 Define $\textbf{\emph{X}},\textbf{\emph{R}}\in\Re^{N}$,
${\textbf{\emph{X}}}_{i}$, ${\textbf{\emph{R}}}_{i}$, and
${\textbf{\emph{e}}}{(j)}$ as each element of error vector e, where
$\textbf{\emph{e}}=\textbf{\emph{X}}-\textbf{\emph{R}},j=1,...,N$. Assume that
${\textbf{\emph{e}}}{(j)}$ follows an independent zero mean distribution with
variance ${\sigma}^{2}$, and thus for any $\varepsilon>0$, we can represent
the relationship between
$\frac{1}{N}||\textbf{\emph{X}}-\textbf{\emph{R}}||_{2}^{2}$ and
${\frac{1}{K}}\sum_{i=1}^{n}||{\textbf{\emph{X}}}_{i}-{\textbf{\emph{R}}}_{i}||_{2}^{2}$
by the following property,

$\lim_{{N\rightarrow\infty}\atop{K\rightarrow\infty}}{\textbf{\emph{P}}}{\\{|\frac{1}{N}||\textbf{\emph{X}}-\textbf{\emph{R}}||_{2}^{2}-{\frac{1}{K}}\sum\nolimits_{i=1}^{n}||{\textbf{\emph{X}}}_{i}-{\textbf{\emph{R}}}_{i}||_{F}^{2}|<\varepsilon\\}}=1$
(27)

where ${\textbf{\emph{P}}}(\bullet)$ represents the probability and
${\emph{K}}=\emph{d}\times\emph{k}\times\emph{n}$. The detailed proof of
Theorem 3 is given in supplemental matarial.

Based on Theorem 3, we have the following equation with a very large
probability (restricted 1) at each iteration,

$\frac{1}{N}||\textbf{\emph{X}}-\textbf{\emph{R}}||_{2}^{2}={\frac{1}{K}}\sum\nolimits_{i=1}^{n}||{\textbf{\emph{X}}}_{i}-{\textbf{\emph{R}}}_{i}||_{F}^{2}$
(28)

Based on Eqs. (26) and (28), we have

$\displaystyle\min\limits_{{{\boldsymbol{\alpha}}}}\frac{1}{2}{||\textbf{\emph{X}}-\textbf{\emph{R}}||_{2}^{2}}+\frac{\lambda}{\rho}||{\textbf{\emph{w}}}_{{\boldsymbol{\alpha}}}||_{p}$
(29)
$\displaystyle=\min\limits_{{{{\boldsymbol{\alpha}}}}_{i}}(\sum\nolimits_{i=1}^{n}\frac{1}{2}||{\textbf{\emph{X}}}_{i}-{\textbf{\emph{R}}}_{i}||_{F}^{2}+{{\tau}}_{i}||{{{\emph{w}}}}_{i}{{{\boldsymbol{\alpha}}}}_{i}||_{p})$
$\displaystyle=\min\limits_{{{{\boldsymbol{\alpha}}}}_{i}}(\sum\nolimits_{i=1}^{n}\frac{1}{2}||{\textbf{\emph{R}}}_{i}-{{\textbf{\emph{D}}}_{i}{{{\boldsymbol{\alpha}}}}_{i}}||_{F}^{2}+{{\tau}}_{i}||{{{\emph{w}}}}_{i}{{{\boldsymbol{\alpha}}}}_{i}||_{p})$

where ${{\tau}}_{i}={{{\lambda}}_{i}{\emph{K}}}/{\rho{\emph{N}}}$ and
${{\textbf{\emph{D}}}_{i}}$ is a dictionary. Clearly, Eq. (29) can be viewed
as a sparse coding problem by solving $n$ sub-problems for all the group
${\textbf{\emph{X}}}_{i}$. Based on _Theorem 1_ , Eq. (29) can be rewritten
as:

${\hat{\boldsymbol{\alpha}}}_{i}=\min\limits_{{{{\boldsymbol{\alpha}}}}_{i}}\sum\nolimits_{i=1}^{n}\frac{1}{2}||{{{{\boldsymbol{\gamma}}}}_{i}}-{{{{\boldsymbol{\alpha}}}}_{i}}||_{2}^{2}+{{\tau}}_{i}{{{\emph{w}}}}_{i}||{{{\boldsymbol{\alpha}}}}_{i}||_{p}$
(30)

where
${\textbf{\emph{R}}}_{i}={{\textbf{\emph{D}}}_{i}{{{\boldsymbol{\gamma}}}}_{i}}$
and
${\textbf{\emph{X}}}_{i}={{\textbf{\emph{D}}}_{i}{{{\boldsymbol{\alpha}}}}_{i}}$.

To obtain the solution of Eq. (30) effectively, in this paper, the generalized
soft-thresholding (GST) algorithm [16] is used to solve Eq. (30). Therefore, a
closed-form solution of Eq. (30) can be computed as

${\hat{\boldsymbol{\alpha}}}_{i}={{\emph{GST}}}({{{\boldsymbol{\gamma}}}}_{i},{{\tau}}_{i}{{{\emph{w}}}}_{i},p)$
(31)

For more details about the GST algorithm, please refer to [16]. For each
weight ${{{\emph{w}}}}_{i}$, large values of sparse coefficient
${{{\boldsymbol{\alpha}}}}_{i}$ usually transmit major edge and texture
information [5]. This implies that to reconstruct ${\textbf{\emph{X}}}_{i}$
from its degraded one, we should shrink large values less, while shrinking
smaller ones more, and thus we have
${{{\emph{w}}}}_{i}=1/(|{{{\boldsymbol{\gamma}}}}_{i}|+\epsilon)$, where
$\epsilon$ is a small constant. Inspired by [17], the regularization parameter
$\lambda_{i}$ of each group ${\textbf{\emph{R}}}_{i}$ is set as:
$\lambda_{i}=2\sqrt{2}\sigma^{2}/(\delta_{i}+\varepsilon)$, where $\delta_{i}$
denotes the estimated variance of ${{{\boldsymbol{\gamma}}}}_{i}$, and
$\varepsilon$ is a small constant. After solving the two sub-problems, we
summarize the overall algorithm for Eq. (19) in _Table 1_.

Table 1: ADMM method for Eq. (19) Input: the observed image Y and the
measurement matrix $\textbf{\emph{H}}.$
---
$\textbf{Initialization:}\ t$, C, Z, ${{\boldsymbol{\alpha}}}$, I, d, k,
$\rho$, $p$, $\sigma$, $\epsilon$, $\varepsilon$;
Repeat
Update ${{\textbf{\emph{Z}}}}^{t+1}$ by Eq. (24);
${\textbf{\emph{R}}}^{{t}+1}={\textbf{\emph{Z}}}^{{t}+1}-{\textbf{\emph{C}}}^{t}$;
For Each group ${\textbf{\emph{R}}}_{i}$;
Construct dictionary ${\textbf{\emph{D}}}_{i}$ by computing Eq. (9);
Update ${\lambda_{i}}^{t+1}$ by computing
$\lambda_{i}=2\sqrt{2}\sigma^{2}/\delta_{i}+\varepsilon$;
Update $\tau_{i}^{t+1}$ computing by
${{\tau}}_{i}={{{\lambda}}_{i}{\emph{K}}}/{\rho{\emph{N}}}$;
Update ${{\emph{w}}}_{i}^{t+1}$ computing by
${{{\emph{w}}}}_{i}={{\tau}}_{i}/|{{{\boldsymbol{\gamma}}}}_{i}|+\epsilon$;
Update ${\boldsymbol{\alpha}}_{i}^{t+1}$ computing by Eq. (31);
End For
Update ${\textbf{\emph{D}}}^{t+1}$ by concatenating all
${\textbf{\emph{D}}}_{i}$ ;
Update ${\boldsymbol{\alpha}}^{t+1}$ by concatenating all
${\boldsymbol{\alpha}}_{i}$ ;
Update ${{\textbf{\emph{C}}}^{t+1}}$ by computing Eq. (22) ;
$t\leftarrow t+1$;
Until
maximum iteration number is reached.
Output:
The final restored image
$\hat{\textbf{\emph{X}}}={\textbf{\emph{D}}}{\hat{\boldsymbol{\alpha}}}.$

Fig. 2: All test images.

Fig. 3: Visual comparison of _Mickey_ by image inpainting with 80% missing
pixels.

Fig. 4: Visual comparison of _Fence_ by CS recovery with 0.1$N$ measurements. Table 2: Average PSNR results (dB) of image inpainting Method | 80% | 70% | 60% | 50% | Inlay text
---|---|---|---|---|---
BPFA | 24.35 | 26.26 | 28.03 | 29.83 | 31.42
IPPO | 25.40 | 27.34 | 29.19 | 30.93 | 32.90
Aloha | 25.13 | 26.92 | 28.51 | 30.13 | 31.12
Proposed | 25.91 | 28.04 | 29.98 | 31.95 | 33.58
Table 3: Average PSNR results (dB) of image CS recovery Ratio | BM3D | ADS | SGSR | MRK | Proposed
---|---|---|---|---|---
0.1 | 24.23 | 27.65 | 27.93 | 27.14 | 28.89
0.2 | 30.60 | 32.42 | 32.36 | 31.22 | 33.50
0.3 | 34.11 | 35.68 | 34.87 | 34.20 | 36.50

##  5 Experimental Results

In this section, we report our experimental results in the applications of
image inpainting and image CS recovery. All the experimental images are shown
in Fig. 2.

In image inpainting, two interesting examples of image inpainting with
different masks are conducted, i.e., image restoration from partial random
samples and text inlayed sample. The parameters are set as follows. The size
of each patch $\sqrt{d}\times\sqrt{d}$ is set to be $8\times 8$ and $10\times
10$ for partial random samples and text inlayed, respectively. Similar patch
numbers $k=60$, $\emph{I}=25$, $\sigma=\sqrt{2}$, $\epsilon=0.1$,
$\varepsilon=0.3$. ($\rho$, $p$) are set to (0.0003, 0.45), (0.0003, 0.45),
(0.03, 1), (0.04, 1) and (0.06, 0.95) when 80%, 70%, 60%, 50% pixels missing
and text inlayed, respectively.

We compared the proposed scheme with three other competing methods: BPFA
method [2], IPPO method [18], Aloha method [19]. Table 2 lists the average
PSNR comparison results for a collection of 10 color images among three
competing methods. The visual comparison of the image inpainting methods is
shown in Fig. 3. It can be seen that BPFA could not reconstruct sharp edges
and fine details. The IPPO and Aloha methods produced images with a much
better visual quality than BPFA method, but still suffered from some
undesirable artifacts, such as the ringing effects. The proposed scheme not
only preserved sharper edges and finer details, but eliminated the ringing
effects.

In image CS recovery, we generated the CS measurements at the block level by
utilizing a Gaussian random projection matrix to test images, i.e., the CS
recovery with block size $32\times 32$. The parameters are set as follows. The
size of each patch $\sqrt{d}\times\sqrt{d}$ is set to be $7\times 7$. Similar
patch numbers $k=60$, $\emph{I}=20$, $\sigma=\sqrt{2}$, $\epsilon=0.1$,
$\varepsilon=0.4$. ($\rho$, $p$) are set to (0.0001, 0.65), (0.0005, 0.5) and
(0.05, 1) when 0.1$N$, 0.2$N$ and 0.3$N$ measurements, respectively.

We have compared the proposed method based image CS recovery against four
other competing approaches including BM3D method [20], ADS method [4], SGSR
method [21] and MRK method [22]. The average PSNR results are shown in Table
3. The average gain of the proposed scheme over BM3D, ADS, SGSR and MRK
methods can be as much as 3.31dB, 1.04dB, 1.24dB and 2.11dB, respectively. The
visual comparisons of the image CS recovery are shown in Fig. 4. It can be
seen that the BM3D, ADS, SGSR, and MRK methods still suffer from some
undesirable artifacts or over-smooth phenomena. By contrast, the proposed
method not only removes most of the visual artifacts, but also preserves
large-scale sharp edges and small-scale fine image details more effectively.

##  6 Conclusion

This paper proposed to analyze the group sparsity based on the rank
minimization methods. An adaptive dictionary learning method for each group is
designed. We prove the equivalence of the group-based sparse coding and the
rank minimization problem, and thus the sparse coefficient of each group are
measured by computing the singular values of each group. Four nuclear norms
are used to analyze the sparsity of each group and the solution of the
weighted Schatten $p$-norm minimization (WSNM) is the best approximation to
real singular values of each group. Therefore, WSNM can be equivalently
transformed into a non-convex $\ell_{p}$-norm minimization problem in group-
based sparse coding. To make the proposed scheme tractable and robust, we
utilize the alternating direction method of multipliers (ADMM) to solve the
$\ell_{p}$-norm minimization problem. Experimental results on image inpainting
and image CS recovery have demonstrated that the proposed scheme achieves
significant performance improvements over the current state-of-the-art
methods.

##  7 Appendix

Consider the SVD of a matrix $\textbf{\emph{P}}\in\Re^{n_{1}\times n_{2}}$ of
rank $r$

$\textbf{\emph{P}}=\textbf{\emph{U}}\boldsymbol{\Sigma}\textbf{\emph{V}}^{T},\boldsymbol{\Sigma}={\rm
diag}(\\{\sigma_{i}\\}_{1\leq i\leq r})$ (32)

where $\textbf{\emph{U}}\in\Re^{n_{1}\times r}$ and
$\textbf{\emph{V}}\in\Re^{n_{2}\times r}$ are orthogonal matrices,
respectively. $\sigma_{i}$ is the $i$-th singular value of P. For each
$\tau\geq 0$, the soft-thresholding operator $\mathcal{D}_{\tau}$ is defined
as

$\mathcal{D}_{\tau}(\textbf{\emph{P}})=\textbf{\emph{U}}\mathcal{D}_{\tau}(\boldsymbol{\Sigma})\textbf{\emph{V}}^{T},\
\ \ \mathcal{D}_{\tau}(\boldsymbol{\Sigma})={\rm soft}(\sigma_{i},\tau)$ (33)

Lemma 2

For each $\tau\geq 0$, and $\textbf{\emph{Q}}\in\Re^{n_{1}\times n_{2}}$ ,the
singular value shrinkage operator Eq. (33) satisfies

$\mathcal{D}_{\tau}(\textbf{\emph{Q}})=\arg\min_{\textbf{\emph{P}}}\\{\frac{1}{2}||{\textbf{\emph{P}}}-{\textbf{\emph{Q}}}||_{F}^{2}+\tau||{\textbf{\emph{P}}}||_{*}\\}$
(34)

_Proof:_ Due to the strict convex of the function
$h(\textbf{\emph{P}}):=\frac{1}{2}||{\textbf{\emph{P}}}-{\textbf{\emph{Q}}}||_{F}^{2}+\tau||{\textbf{\emph{P}}}||_{*}$,
it is easy to observe that there exists an unique minimizer, and thus we are
only required to prove that it is equal to
$\mathcal{D}_{\tau}({\textbf{\emph{Q}}})$. To this end, recall the definition
of a subgradient of a convex function $f:\Re^{n_{1}\times
n_{2}}\rightarrow\Re$. We say that Z is a subgradient of $f$ at
${\textbf{\emph{P}}}_{0}$, denoted $\textbf{\emph{Z}}\in\partial
f({\textbf{\emph{P}}}_{0})$, if

$f({\textbf{\emph{P}}})\geq
f({\textbf{\emph{P}}}_{0})+\langle\textbf{\emph{Z}},{\textbf{\emph{P}}}-{\textbf{\emph{P}}}_{0}\rangle$
(35)

for all P. Now $\hat{\textbf{\emph{P}}}$ minimizes $h$ if and only if it
satisfies the following optimal condition, i.e.,

$\textbf{0}\in\hat{\textbf{\emph{P}}}-{\textbf{\emph{Q}}}+\tau\partial||\hat{\textbf{\emph{P}}}||_{*}$
(36)

where $\partial||\hat{\textbf{\emph{P}}}||_{*}$ is the set of subgradients of
the nuclear norm. Let matrix ${\textbf{\emph{P}}}\in\Re^{n_{1}\times n_{2}}$
and its SVD be $\textbf{\emph{U}}\boldsymbol{\Sigma}\textbf{\emph{V}}^{T}$. It
is known from [23] that the subgradient of $||{\textbf{\emph{P}}}||_{*}$ can
be derived as

$\partial||{\textbf{\emph{P}}}||_{*}=\\{\textbf{\emph{U}}\textbf{\emph{V}}^{T}+\textbf{\emph{S}}:\
\ \textbf{\emph{S}}\in\Re^{n_{1}\times
n_{2}},\textbf{\emph{U}}^{T}\textbf{\emph{S}}=0,\textbf{\emph{S}}\textbf{\emph{V}}=0,||\textbf{\emph{S}}||_{2}\leq
1\\}$ (37)

We set $\hat{\textbf{\emph{P}}}=\mathcal{D}_{\tau}({\textbf{\emph{Q}}})$, to
show that $\hat{\textbf{\emph{P}}}$ satisfies Eq. (36), we rewritten the SVD
of Q as
$\textbf{\emph{Q}}=\textbf{\emph{U}}_{0}\boldsymbol{\Sigma}_{0}\textbf{\emph{V}}_{0}^{T}+\textbf{\emph{U}}_{1}\boldsymbol{\Sigma}_{1}\textbf{\emph{V}}_{1}^{T}$,
where $\textbf{\emph{U}}_{0},\textbf{\emph{V}}_{0}({\rm
resp}.\textbf{\emph{U}}_{1},\textbf{\emph{V}}_{1})$ are the singular vectors
associated with singular values greater than $\tau$ (resp. smaller than or
equal to $\tau$). With these notations, we have

$\hat{\textbf{\emph{P}}}=\textbf{\emph{U}}_{0}(\boldsymbol{\Sigma}_{0}-\tau\textbf{\emph{I}})\textbf{\emph{V}}_{0}^{T}$
(38)

Therefore,

$\textbf{\emph{Q}}-\hat{\textbf{\emph{P}}}=\tau(\textbf{\emph{U}}_{0}\textbf{\emph{V}}_{0}^{T}+\textbf{\emph{S}}),\
\
\textbf{\emph{S}}=\tau^{-1}\textbf{\emph{U}}_{1}\boldsymbol{\Sigma}_{1}\textbf{\emph{V}}_{1}^{T}$
(39)

By definition,
$\textbf{\emph{U}}_{0}^{T}\textbf{\emph{S}}=0,\textbf{\emph{S}}\textbf{\emph{V}}_{0}=0.$
Since the diagonal elements of $\boldsymbol{\Sigma}_{1}$ have magnitudes
bounded by $\tau$, we also have $||\textbf{\emph{S}}||_{2}\leq 1.$ Therefore,
$\textbf{\emph{Q}}-\hat{\textbf{\emph{P}}}\in\tau\partial||\hat{\textbf{\emph{P}}}||_{*}$,
which concludes the proof.

Theorem 1

$||{\textbf{\emph{Y}}}_{i}-{\textbf{\emph{X}}}_{i}||_{F}^{2}=||\boldsymbol{\mu}_{i}-\boldsymbol{\alpha}_{i}||_{2}^{2}$
(40)

where ${\textbf{\emph{Y}}}_{i}={\textbf{\emph{D}}}_{i}\boldsymbol{\mu}_{i}$
and ${\textbf{\emph{X}}}_{i}={\textbf{\emph{D}}}_{i}\boldsymbol{\alpha}_{i}$.

_Proof:_ Since the adaptive dictionary ${\textbf{\emph{D}}}_{i}$ is
constructed by Eq. (9), and the unitary property of ${\textbf{\emph{U}}}_{i}$
and ${\textbf{\emph{V}}}_{i}$, we have

$\displaystyle||{\textbf{\emph{Y}}}_{i}-{\textbf{\emph{X}}}_{i}||_{F}^{2}=||{\textbf{\emph{D}}}_{i}(\boldsymbol{\mu}_{i}-\boldsymbol{\alpha}_{i})||_{F}^{2}=||{\textbf{\emph{U}}}_{i}{\rm
diag}(\boldsymbol{\mu}_{i}-\boldsymbol{\alpha}_{i}){\textbf{\emph{V}}}_{i}||_{F}^{2}$
(41) $\displaystyle={\rm trace}({\textbf{\emph{U}}}_{i}{\rm
diag}({{{{\boldsymbol{\mu}}}_{\textbf{\emph{G}}}}_{i}}-{{{{\boldsymbol{\alpha}}}_{\textbf{\emph{G}}}}_{i}}){\textbf{\emph{V}}}_{i}{\textbf{\emph{V}}}_{i}^{T}{\rm
diag}(\boldsymbol{\mu}_{i}-\boldsymbol{\alpha}_{i}){\textbf{\emph{U}}}_{i}^{T})$
$\displaystyle={\rm trace}({\textbf{\emph{U}}}_{i}{\rm
diag}(\boldsymbol{\mu}_{i}-\boldsymbol{\alpha}_{i}){\rm
diag}(\boldsymbol{\mu}_{i}-\boldsymbol{\alpha}_{i}){\textbf{\emph{U}}}_{i}^{T})$
$\displaystyle={\rm trace}({\rm
diag}(\boldsymbol{\mu}_{i}-\boldsymbol{\alpha}_{i}){\textbf{\emph{U}}}_{i}{\textbf{\emph{U}}}_{i}^{T}{\rm
diag}(\boldsymbol{\mu}_{i}-\boldsymbol{\alpha}_{i}))$ $\displaystyle={\rm
trace}({\rm diag}(\boldsymbol{\mu}_{i}-\boldsymbol{\alpha}_{i}){\rm
diag}(\boldsymbol{\mu}_{i}-\boldsymbol{\alpha}_{i}))$
$\displaystyle=||\boldsymbol{\mu}_{i}-\boldsymbol{\alpha}_{i}||_{2}^{2}$

This completes the proof of the theorem.

Theorem 2

The equivalence of the group-based sparse coding and the rank minimization
problem is satisfied under the dictionary ${\textbf{\emph{D}}}_{i}$.

_Proof:_ On the basis of Theorem 1, we have

$\displaystyle{{\boldsymbol{\alpha}}}_{i}$
$\displaystyle=\arg\min\limits_{\boldsymbol{\alpha}_{i}}\\{\frac{1}{2}||{\textbf{\emph{Y}}}_{i}-{\textbf{\emph{D}}}_{i}{\boldsymbol{\alpha}}_{i}||_{F}^{2}+\lambda||{\boldsymbol{\alpha}}_{i}||_{1}\\}$
(42)
$\displaystyle=\arg\min\limits_{\boldsymbol{\alpha}_{i}}\\{\frac{1}{2}||{\boldsymbol{\mu}}_{i}-{\boldsymbol{\alpha}}_{i}||_{2}^{2}+\lambda||{\boldsymbol{\alpha}}_{i}||_{1}\\}$

Thus, based on Lemma 1, we have

$\displaystyle{{\boldsymbol{\alpha}}}_{i}$ $\displaystyle={\rm
soft}({{\boldsymbol{\mu}}}_{i},\lambda)={\rm
sgn}({{\boldsymbol{\mu}}}_{i},\lambda).{\rm
max}(abs({{\boldsymbol{\mu}}}_{i})-\lambda,0)$ (43)

Obviously, according to Eqs. (8) and (9), we have

$\displaystyle{\textbf{\emph{D}}}_{i}{{\boldsymbol{\alpha}}}_{i}=\sum\nolimits_{j=1}^{m}{{\rm
soft}({\boldsymbol{\mu}}}_{i,j},\lambda){\textbf{\emph{d}}}_{i,j}$ (44)
$\displaystyle=\sum\nolimits_{j=1}^{m}{{\rm
soft}({\boldsymbol{\mu}}}_{i,j},\lambda){\textbf{\emph{u}}}_{i,j}{\textbf{\emph{v}}}_{i,j}^{T}$
$\displaystyle={\textbf{\emph{U}}}_{i}\mathcal{D}_{\tau}(\boldsymbol{\Sigma}_{i}){\textbf{\emph{V}}}_{i}^{T}$

where ${{\boldsymbol{\alpha}}}_{i,j}$ represents the $j$-th element of the
$i$-th group sparse coefficient ${{\boldsymbol{\alpha}}}_{i}$, and
$\boldsymbol{\Sigma}_{i}$ is the singular value matrix of the $i$-th group
${\textbf{\emph{Y}}}_{i}$.

Thus, based on _Lemma 2_ , we prove that the group-based sparse coding (Eq.
(42)) is equivalent to the rank minimization problem (Eq. (34)).

Note that the main difference between sparse coding and the rank minimization
problem is that sparse coding has a dictionary learning operator and the rank
minimization problem does not involve.

Theorem 3

Define $\textbf{\emph{X}},\textbf{\emph{R}}\in\Re^{N}$,
${\textbf{\emph{X}}}_{i}$, ${\textbf{\emph{R}}}_{i}$, and
${\textbf{\emph{e}}}{(j)}$ as each element of error vector e, where
$\textbf{\emph{e}}=\textbf{\emph{X}}-\textbf{\emph{R}},j=1,...,N$. Assume that
${\textbf{\emph{e}}}{(j)}$ follows an independent zero mean distribution with
variance ${\sigma}^{2}$, and thus for any $\varepsilon>0$, we can represent
the relationship between
$\frac{1}{N}||\textbf{\emph{X}}-\textbf{\emph{R}}||_{2}^{2}$ and
${\frac{1}{K}}\sum_{i=1}^{n}||{\textbf{\emph{X}}}_{i}-{\textbf{\emph{R}}}_{i}||_{2}^{2}$
by the following property, namely,

$\lim_{{N\rightarrow\infty}\atop{K\rightarrow\infty}}{\textbf{\emph{P}}}{\\{|\frac{1}{N}||\textbf{\emph{X}}-\textbf{\emph{R}}||_{2}^{2}-{\frac{1}{K}}\sum\nolimits_{i=1}^{n}||{\textbf{\emph{X}}}_{i}-{\textbf{\emph{R}}}_{i}||_{F}^{2}|<\varepsilon\\}}=1$
(45)

where ${\textbf{\emph{P}}}(\bullet)$ represents the probability and
${\emph{K}}=\emph{d}\times\emph{k}\times\emph{n}$.

_Proof:_ Owing to the assumption that
${\textbf{\emph{e}}}{(\textbf{\emph{j}})}$ follows an independent zero mean
distribution with variance $\sigma^{2}$, namely,
$\textbf{\emph{E}}[{\textbf{\emph{e}}}{(\textbf{\emph{j}})}]=0$ and
$\textbf{\emph{Var}}[{\textbf{\emph{e}}}{(\textbf{\emph{j}})}]=\sigma^{2}$.
Thus, it can be deduced that each
${\textbf{\emph{e}}}{(\textbf{\emph{j}})}^{2}$ is also independent, and the
meaning of each ${\textbf{\emph{e}}}{(\textbf{\emph{j}})}^{2}$ is:

$\textbf{\emph{E}}[{\textbf{\emph{e}}}{(\textbf{\emph{j}})}^{2}]=\textbf{\emph{Var}}[{\textbf{\emph{e}}}{(\textbf{\emph{j}})}]+[\textbf{\emph{E}}[{\textbf{\emph{e}}}{(\textbf{\emph{j}})}]]^{2}=\sigma^{2},\emph{j}=1,2,...,\emph{N}$
(46)

By invoking the law of Large numbers in probability theory, for any
$\epsilon>0$, it leads to
$\lim\limits_{\emph{N}\rightarrow\infty}{\textbf{\emph{P}}}\\{|\frac{1}{\emph{N}}\Sigma_{\emph{j}=1}^{\emph{N}}{\textbf{\emph{e}}}{(\textbf{\emph{j}})}^{2}-\sigma^{2}|<\frac{\epsilon}{2}\\}=1$,
namely,

$\lim\limits_{\emph{N}\rightarrow\infty}{\textbf{\emph{P}}}\\{|\frac{1}{\emph{N}}||\textbf{\emph{X}}-\textbf{\emph{R}}||_{2}^{2}-\sigma^{2}|<\frac{\epsilon}{2}\\}=1$
(47)

Next, we denote the concatenation of all the groups ${\textbf{\emph{X}}}_{i}$
and ${\textbf{\emph{R}}}_{i},\ \emph{i}=1,2,...,\emph{n}$, by X and R,
respectively. Meanwhile, we denote the error of each element of
${\textbf{\emph{X}}}-{\textbf{\emph{R}}}$ by
${\textbf{\emph{e}}}{\emph{(k)}},\ \emph{k}=1,2,...,\emph{K}$. We have also
denote e(k) following an independent zero mean distribution with variance
$\sigma^{2}$.

Therefore, the same process applied to ${\textbf{\emph{e}}}{\emph{(k)}}^{2}$
yields
$\lim\limits_{\emph{N}\rightarrow\infty}{\textbf{\emph{P}}}\\{|\frac{1}{\emph{N}}\Sigma_{\emph{k}=1}^{\emph{N}}{\textbf{\emph{e}}}{({\emph{k}})}^{2}-\sigma^{2}|<\frac{\epsilon}{2}\\}=1$,
i.e.,

$\lim\limits_{\emph{N}\rightarrow\infty}{\textbf{\emph{P}}}\\{|\frac{1}{\emph{N}}\Sigma_{\emph{i}=1}^{\emph{n}}||{\textbf{\emph{X}}}_{i}-{\textbf{\emph{R}}}_{i}||_{2}^{2}-\sigma^{2}|<\frac{\epsilon}{2}\\}=1$
(48)

Obviously, considering Eqs. (47) and (48) together, we can prove Eq. (45).

##  8 Acknowledge

The authors would like to thank Dr. Jian Zhang 111
http://124.207.250.90/staff/zhangjian/ of Peking University for his help. In
addition, this work was supported by the NSFC (61571220, 61462052, 61502226)
and the open research fund of National Mobile Commune. Research Lab.,
Southeast University (No.2015D08).

## References

  * [1] Elad M, Aharon M. Image denoising via sparse and redundant representations over learned dictionaries[J]. IEEE Transactions on Image processing, 2006, 15(12): 3736-3745.
  * [2] Zhou M, Chen H, Ren L, et al. Non-parametric Bayesian dictionary learning for sparse image representations[C]//Advances in neural information processing systems. 2009: 2295-2303.
  * [3] Zhang J, Zhao D, Gao W. Group-based sparse representation for image restoration[J]. IEEE Transactions on Image Processing, 2014, 23(8): 3336-3351.
  * [4] Dong W, Shi G, Li X, et al. Image reconstruction with locally adaptive sparsity and nonlocal robust regularization[J]. Signal Processing: Image Communication, 2012, 27(10): 1109-1122.
  * [5] Candes E J, Wakin M B, Boyd S P. Enhancing sparsity by reweighted $\ell_{1}$ minimization[J]. Journal of Fourier analysis and applications, 2008, 14(5-6): 877-905.
  * [6] Mairal J, Bach F, Ponce J, et al. Non-local sparse models for image restoration[C]//2009 IEEE 12th International Conference on Computer Vision. IEEE, 2009: 2272-2279.
  * [7] Cand s E J, Romberg J, Tao T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on information theory, 2006, 52(2): 489-509.
  * [8] Cai J F, Cand s E J, Shen Z. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20(4): 1956-1982.
  * [9] Gu S, Xie Q, Meng D, et al. Weighted nuclear norm minimization and its applications to low level vision[J]. International Journal of Computer Vision, 2016: 1-26.
  * [10] Nie F, Huang H, Ding C H Q. Low-Rank Matrix Recovery via Efficient Schatten p-Norm Minimization[C]//AAAI. 2012.
  * [11] Xie Y, Gu S, Liu Y, et al. Weighted Schatten $p$-Norm Minimization for Image Denoising and Background Subtraction[J]. IEEE transactions on image processing, 2016,10(25),1057-7149.
  * [12] Ke Q, Kanade T. Robust $\ell_{1}$ norm factorization in the presence of outliers and missing data by alternative convex programming[C]//2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05). IEEE, 2005, 1: 739-746.
  * [13] Eriksson A P, Van Den Hengel A. Efficient computation of robust low-rank matrix approximations in the presence of missing data using the L1 norm[C]//CVPR. 2010, 1(2): 4.
  * [14] Li C, Yin W, Zhang Y. User s guide for TVAL3: TV minimization by augmented lagrangian and alternating direction algorithms[J]. CAAM report, 2009, 20: 46-47.
  * [15] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends? in Machine Learning, 2011, 3(1): 1-122.
  * [16] Zuo W, Meng D, Zhang L, et al. A generalized iterated shrinkage algorithm for non-convex sparse coding[C]//Proceedings of the IEEE international conference on computer vision. 2013: 217-224.
  * [17] Chang S G, Yu B, Vetterli M. Adaptive wavelet thresholding for image denoising and compression[J]. IEEE transactions on image processing, 2000, 9(9): 1532-1546.
  * [18] Ram I, Elad M, Cohen I. Image processing using smooth ordering of its patches[J]. IEEE transactions on image processing, 2013, 22(7): 2764-2774.
  * [19] Jin K H, Ye J C. Annihilating filter-based low-rank Hankel matrix approach for image inpainting[J]. IEEE Transactions on Image Processing, 2015, 24(11): 3498-3511.
  * [20] Egiazarian K, Foi A, Katkovnik V. Compressed sensing image reconstruction via recursive spatially adaptive filtering[C]//2007 IEEE International Conference on Image Processing. IEEE, 2007, 1: I-549-I-552.
  * [21] Zhang J, Zhao D, Jiang F, et al. Structural group sparse representation for image compressive sensing recovery[C]//Data Compression Conference (DCC), 2013. IEEE, 2013: 331-340.
  * [22] Canh T N, Dinh K Q, Jeon B. Multi-scale/multi-resolution Kronecker compressive imaging[C]//Image Processing (ICIP), 2015 IEEE International Conference on. IEEE, 2015: 2700-2704.
  * [23] Cand s E J, Recht B. Exact matrix completion via convex optimization[J]. Foundations of Computational mathematics, 2009, 9(6): 717-772.


MI-HET-824

# The Beam-Dump Ceiling and Its Experimental Implication:
The Case of a Portable Experiment

Doojin Kim<EMAIL_ADDRESS>Mitchell Institute for Fundamental Physics and
Astronomy, Department of Physics and Astronomy, Texas A&M University, College
Station, TX 77843, USA  Jaehoon Yu<EMAIL_ADDRESS>Department of Physics,
University of Texas, Arlington, TX 76019, USA  Jong-Chul Park
<EMAIL_ADDRESS>Department of Physics and IQS, Chungnam National University,
Daejeon 34134, Republic of Korea  Hyunyong Kim<EMAIL_ADDRESS>Mitchell
Institute for Fundamental Physics and Astronomy, Department of Physics and
Astronomy, Texas A&M University, College Station, TX 77843, USA

###### Abstract

We generalize the nature of the so-called beam-dump ``ceiling'' beyond which
the improvement on the sensitivity reach in the search for fast-decaying
mediators dramatically slows down, and point out its experimental implications
that motivate tabletop-size beam-dump experiments for the search. Light
(bosonic) mediators are well-motivated new-physics particles as they can
appear in dark-sector portal scenarios and models to explain various
laboratory-based anomalies. Due to their low mass and feebly interacting
nature, beam-dump-type experiments, utilizing high-intensity particle beams
can play a crucial role in probing the parameter space of visibly decaying
such mediators, in particular, the ``prompt-decay'' region where the mediators
feature relatively large coupling and mass. We present a general and semi-
analytic proof that the ceiling effectively arises in the prompt-decay region
of an experiment and show its insensitivity to data statistics, background
estimates, and systematic uncertainties, considering a concrete example, the
search for axion-like particles interacting with ordinary photons at three
benchmark beam facilities, PIP-II at FNAL and SPS and LHC-dump at CERN. We
then identify optimal criteria to perform a cost-effective and short-term
experiment to reach the ceiling, demonstrating that very short-baseline
compact experiments enable access to the parameter space unreachable thus far.

Introduction. Although the Standard Model (SM) provides a successful
description of elementary particles and their mutual interactions, many issues
remain unresolved. For example, the non-vanishing masses of neutrinos and the
existence of dark matter are unexplained by the SM, demanding new physics
beyond the SM. Furthermore, various experimental anomalies, e.g., ATOMKI
Krasznahorkay  _et al._ (2016, 2019, 2021, 2022, 2023), $g_{\mu}-2$ Bennett
_et al._ (2006); Abi  _et al._ (2021); Aguillard  _et al._ (2023), LSND
Aguilar-Arevalo  _et al._ (2001), MiniBooNE Aguilar-Arevalo  _et al._ (2009,
2018, 2021), etc, are hinting the existence of new physics.

Well-motivated explanations of these phenomena are deeply related to new
particles that are very weakly or feebly interacting with the SM particles. In
particular, new bosonic particles with MeV-range masses have been popular
choices to address these observational anomalies and phenomena while
satisfying the existing constraints. As a theoretical approach, the ideas of
portal scenarios such as (pseudo)scalar and vector portals (see, e.g., Ref.
Batell  _et al._ (2022)) promote these MeV-scale particles to the mediators
through which the dark-sector particles, including dark matter can communicate
with the SM particles, and they often motivate MeV-scale light thermal dark
matter. Therefore, searches for mediators of this sort can be regarded as an
alternative avenue for dark-matter detection, especially in an accelerator-
based experiment.

Considering the expected mass range of these particles (henceforth
collectively called mediators), fixed-target experiments such as beam-dump-
type experiments are better suited than the energy-frontier facilities like
the Large Hadron Collider (LHC) to probe MeV-scale physics as their beam
energy is as large as $\mathcal{O}$(1-100 GeV). Moreover, their high
instantaneous intensity particle beams enable the production of feebly-
interacting mediators. For these reasons, the search prospects of (MeV-scale)
Higgs-portal scalars, axion-like particles (ALPs), light $Z^{\prime}$, dark
photon, etc, have been extensively investigated in the beam-dump-type
experiments, especially, ongoing/upcoming/proposed experiments such as CCM,
COHERENT, DUNE, FASER/FASER$\nu$, ICARUS, MicroBooNE, SBND, and SHiP (see also
e.g., Refs. Batell  _et al._ (2022); Ilten  _et al._ (2018); Bauer  _et al._
(2018); Fabbrichesi  _et al._ (2020); Fortin  _et al._ (2021), and references
therein).

A major goal of the experiments above is to expand the search as much as
possible into the ``prompt-decay'' region in which none of the existing
laboratory-based experiments or astrophysical/cosmological considerations have
been able to constrain; a mediator belonging to this region would decay rather
earlier due to its (relatively) large coupling and/or large mass value. A
recent ambitious proposal DAMSA Jang  _et al._ (2023) – in which the detector
system is placed extremely close to the signal source point (i.e., beam target
or dump 111From now on, we will use beam target and dump interchangeably as we
will show that the target width does not affect our results.) – showed the
capability to start probing deeper into the prompt-decay region. Indeed, it
has recently been demonstrated that there exists an inherent limitation dubbed
beam-dump ``ceiling'' beyond which the sensitivity improvement slows down
dramatically so that an ordinary beam-dump-type experiment would have
difficulty probing unless with a nonsensical increase of data statistics Dutta
_et al._ (2023). The actual location of the ceiling crucially depends on the
beam energy and the detector distance from the beam target Dutta  _et al._
(2023).

An important implication of the above observations with the beam-dump ceiling
is that a collection of large amounts of data is no longer necessary to reach
sensibly achievable sensitivity limits. In this context, we delve into the
robustness of the sensitivity reaches near the beam-dump ceiling against the
overall/instantaneous beam intensity, the detector geometry (size and angular
coverage), and underlying background/systematic uncertainty assumptions,
taking three benchmark beam facilities, PIP-II Ainsworth  _et al._ (2021) at
FNAL and SPS Ahdida  _et al._ (2020) and LHC-dump Maestre  _et al._ (2021) at
CERN. From this investigation, we will demonstrate that a tabletop-size
detector system can probe the prompt-decay region of MeV-scale mediators
rather quickly. Therefore, one can imagine experimenting at one beam facility
for a short period until the ceiling has reached and taking the same detector
system to a different beam facility to perform another experiment to expand
the ceiling. Inspired by DAMSA Jang  _et al._ (2023) now being proposed to
PIP-II LINAC, we propose the concept of a portable DAMSA that could
subsequently be performed at other facilities with various beam energies.

Dependence on total beam intensity. We begin with a very rough sketch of the
existing constraints of a generic (bosonic) mediator, say $\varphi$ (e.g.,
ALPs, dark photon, and light $Z^{\prime}$), in FIG. 1. Regions I and II are
constrained by collider and beam-dump searches, respectively, whereas region
III is constrained by various astrophysical and cosmological considerations
including SN1987a, cosmic microwave backgrounds, and big-bang nucleosynthesis.
Region IV is open and can be reached by increasing the statistics. Our primary
interest, however, is to extend the beam-dump reach to region V, i.e., the
prompt-decay region mentioned earlier.

Figure 1: A schematic diagram of the existing constraints on generic
mediators.

In generic beam-dump or fixed-target experiments, if a mediator is produced
inside the dump or target, it should reach and decay into visible particles
within the detector fiducial volume, in order for it to be detected. This
requirement can be formulated as a detection probability $P_{\rm det}$ in
terms of the exponential decay law:

$P_{\rm det}=\exp\left(-\frac{L_{\rm
dist}}{\tilde{l}_{\varphi}}\right)\left[1-\exp\left(-\frac{\Delta L_{\rm
det}}{\tilde{l}_{\varphi}}\right)\right]\,,$ (1)

where $L_{\rm dist}$ and $\Delta L_{\rm det}$ denote the detector distance
from the signal production point and the detector size along the direction of
the mediator, respectively. $\tilde{l}_{\varphi}$ is the mean decay length of
$\varphi$ in the laboratory frame. Note that the smaller the $L_{\rm dist}$,
the larger the $P_{\rm det}$. By definition,

$L_{\rm dist},\Delta L_{\rm det}\gg\tilde{l}_{\varphi}$ (2)

in the prompt-decay region, resulting in $P_{\rm det}\approx\exp(-L_{\rm
dist}/\tilde{l}_{\varphi})$.

Suppose that for a given mass $m_{\varphi}$, an experiment can reach a
coupling value $g$ with $N$ source particles inducing the $\varphi$
production. If data statistics increases (via beam intensity or beam exposure
duration) by a factor of $X$, the new sensitivity reach $g^{\prime}$ is given
by (Dutta  _et al._ , 2023)

$g^{\prime}\approx g\left(1+\frac{\log X}{\log(N\langle P_{\rm
prod}\rangle/N_{\rm req})-1}\right)^{1/2}\,,$ (3)

where $N_{\rm req}$ is the number of signal events required to define the
sensitivity reach $g$, and $\langle P_{\rm prod}\rangle$ is the average
mediator production probability at $g$ for the given source particle. For a
large background, $\log X$ can be replaced with $\log X^{1/2}$.

In ongoing/planned beam-dump or fixed-target experiments, particle beams are
highly intensified, hence $N$ is very large. In the prompt-decay region, the
coupling is not too small and so is $\langle P_{\rm prod}\rangle$. Finally,
unless an experiment suffers from poor background rejection or poor
understanding of systematic uncertainties, $N_{\rm req}$ needs not be too
large. Therefore, the denominator in Eq. (3) is larger than the numerator, as
long as $X$ is at a sensible level. This implies that any feasible level of an
increase in data collection would not allow for an appreciable improvement in
the sensitivity reach. This conversely implies that decreasing data collection
would not result in a considerable degradation in the sensitivity reach, as
long as $|\log X|\ll\log(N\langle P_{\rm prod}\rangle/N_{\rm req})-1$. The
overall decrease in data collection can be done in two ways:

  * ($a$)

smaller beam exposure,

  * ($b$)

smaller beam power.

Dependence on background and systematic uncertainty estimates. A similar
exercise can be done for the case where a different number of signal events
$N_{\rm req}^{\prime\prime}$ is required to determine the sensitivity reach.
For example, one could incorrectly estimate backgrounds and/or systematics so
that the true sensitivity reach would have been $g^{\prime\prime}$. We find
that $g^{\prime\prime}$ is expressed as

$g^{\prime\prime}\approx g\left(1+\frac{\log(N_{\rm req}^{\prime\prime}/N_{\rm
req})}{\log(N\langle P_{\rm prod}\rangle/N_{\rm req})-1}\right)^{-1/2}\,.$ (4)

This relation suggests that unless an estimate of backgrounds or systematics
is very poorly done, the numerator $|\log(N_{\rm req}^{\prime\prime}/N_{\rm
req})|$ is much smaller than the denominator $\log(N\langle P_{\rm
prod}\rangle/N_{\rm req})-1$, making $g^{\prime\prime}$ differ insignificantly
from $g$.

All these observations demonstrate that the sensitivity near the beam-dump
ceiling is robust and nearly insensitive to details of backgrounds,
systematics, and beam intensity unless they are grossly misestimated. We will
verify this expectation shortly in a (semi-)quantitative way, taking the ALP
interacting with the SM photon as a concrete example.

Dependence on detector geometry. Many experiments that aim to detect mediator
decay signals often accompany a finite-size decay volume or equivalent module
immediate upstream of the particle detection modules (e.g., DAMSA Jang  _et
al._ (2023), DarkQuest Apyan  _et al._ (2022), NA62 Cortina Gil  _et al._
(2017), SHiP Alekhin  _et al._ (2016), etc). Obviously, the mediators residing
near the ceiling are likely to decay promptly, and thus a long decay volume is
unessential to probe this region. More specifically, decay events contributing
to the sensitivity determination near the ceiling mostly happen at the
beginning of the decay volume. Therefore, the sensitivity reaches in the
prompt-decay region are nearly unaffected by the length of decay volume.

Furthermore, the prompt mediators that reach and decay in the decay volume are
likely to be highly boosted. Mediators with a large boost factor are induced
by high-energetic, more forward-directed source particles. Therefore, wide
angular coverage is less motivated, in order for a detector to explore the
prompt-decay region.

Considering the above two geometry-wise observations that are summarized as

  * ($c$)

shorter length of the decay volume,

  * ($d$)

smaller angular coverage of the detector system,

we expect that a tabletop-size detector system can, in principle, be
sufficient to probe the prompt-decay region and reach its own beam-dump
ceiling. We will show the dependence of sensitivity reaches on these aspects
again in the context of the ALP scenario.

Dependence on instantaneous beam intensity. The discussion thus far is
relevant to any generic mediators irrespective of whether or not their visible
decay products involve some features that are distinguishable from potential
(reducible) backgrounds. Depending on the final-state features in the mediator
decay, an appropriate choice of instantaneous beam intensity (i.e., single-
bunch intensity) would further reduce the required beam exposure to achieve
the aimed sensitivity goal in the prompt-decay region. For example, in the
DAMSA proposal Jang  _et al._ (2023), the authors studied the ALP decaying to
a photon pair and identified an accidental overlap of a pair of beam-related-
neutron-induced photons that mimics the di-photon signal as the primary
background.

One can expect that the number of background events will be reduced if the
number of beam-related-neutron-induced photons in a single beam bunch length
decreases. For a more quantitative calculation, suppose that a given protons-
on-target (PoT) is delivered by $n_{\rm bunch}$ beam bunches, and each bunch
results in $n_{\gamma}$ neutron-induced photons (possibly after a set of
cuts). Since the number of photon pairs within the given beam bunch is $\sim
n_{\gamma}^{2}$, the total number of signal-faking accidental photon pairs in
the given PoT is $\sim n_{\rm bunch}n_{\gamma}^{2}$. Therefore, if the same
PoT is delivered by an $f$ times more bunches, the number of beam-related-
neutron-induced photons in a beam bunch is $\sim n_{\gamma}/f$, and the
expected total number of backgrounds will be reduced by a factor of $f$ to
$\sim n_{\gamma}^{2}/f$.

This simple algebra clearly shows that while the backgrounds such as the beam-
related-neutron-induced could be formidable, an experiment to perform a search
for featureful mediator signals could benefit greatly in reaching its ceiling
at a lower beam exposure with

  * ($e$)

smaller instantaneous beam intensity.

As this is related to backgrounds, we study the sensitivity dependence to the
instantaneous beam intensity by varying background estimates.

Benchmark study. We are now in the position to validate the arguments thus far
in the context of actual analyses for an example physics case. To this end, we
consider ALPs interacting with the SM photon:

$-\mathcal{L}_{\rm
int}\supset\frac{1}{4}g_{a\gamma\gamma}aF_{\mu\nu}\tilde{F}^{\mu\nu}\,,$ (5)

where $a$, $F_{\mu\nu}$ ($\tilde{F}_{\mu\nu}$), and $g_{a\gamma\gamma}$ are
the ALP field, the (dual-)field strength tensor of the SM photon, and the
interaction strength between the ALP and the SM photon, respectively. Under
this Lagrangian, an ALP is produced by the Primakoff scattering process of the
photons Primakoff (1951) inside the beam target, and it decays into a photon
pair inside the experimental system.

Beam |  $E_{p}$ [GeV] | PoT/bunch | PoT/yr |  $E_{\gamma,{\rm cut}}$ [GeV]
---|---|---|---|---
PIP-II Ainsworth  _et al._ (2021) | 0.8 | $7.7\times 10^{7}$ | $4\times 10^{23}$ | 0.1
SPS Ahdida  _et al._ (2020) | 400 | $5.1\times 10^{4}$ | $4\times 10^{19}$ | 5
LHC-dump Maestre  _et al._ (2021) | 7,000 | $2.2\times 10^{11}$ | $1.1\times 10^{17}$ | 20

Table 1: Benchmark beam facilities: key beam parameters (2nd-through-4th
columns) and our analysis cuts on photons at ECAL (5th column).

The three benchmark beam facilities and their key specifications are
summarized in Table 1. The photon flux expected in each of the beam facilities
is estimated using GEANT4 Agostinelli  _et al._ (2003). We assume a tungsten
dump for the three beam facilities for comparison purposes, but our
conclusions do not depend on the choice of the dump as long as the material is
the same. The selected target lengths are 1 meter (PIP-II), 1.2 meters (SPS),
and 1.2 meters (LHC-dump), and our simulation shows that the mean photon
production positions are at $\sim 5$ cm, $\sim 15$ cm, and $\sim 20$ cm after
$E_{\gamma,{\rm cut}}$ in Table 1, respectively. We then envision a similar
experimental setup as in the DAMSA proposal Jang  _et al._ (2023); a certain
length of vacuum decay chamber follows from the beam-target system and an
electromagnetic calorimeter (ECAL) is placed downstream of the decay chamber.
We further assume a 100-MeV photon energy threshold and a 1∘ angular
resolution of the detector although the detailed ECAL capabilities nearly
unaffect our conclusions. Finally, we follow the same data analysis scheme and
beam-related-neutron-induced background suppression strategy as explicated in
Ref. Jang  _et al._ (2023).

Figure 2: Expected 90% C.L. sensitivity reaches for coupling
$g_{a\gamma\gamma}$ as a function of ALP mass $m_{a}$ at ($a$) PIP-II, ($b$)
SPS, and ($c$) LHC-dump. The inset in ($a$) shows the fractional change of the
sensitivity with respect to the default case. We compare the three benchmark
beam facilities for $\Delta L_{\rm det}=1$ meter, $\theta_{\rm det}=0.05$ rad,
and $N_{\rm yr}=3$ months in ($d$) where the sensitivity reaches with the
default setup are shown by dotted lines [i.e., the red solid curves in ($a$),
($b$), and ($c$)] for reference purposes.

We first consider PIP-II providing an 800-MeV proton beam and show the
expected 90% C.L. sensitivity reaches under various experimental environments
in FIG. 2($a$). The reference or default parameters are defined as follows:

  * •

detector distance from the mean photon production position in the target,
$L_{\rm dist}=1$ meter,

  * •

length of the decay volume $\Delta L_{\rm det}=10$ meters,

  * •

half the detector opening angle $\theta_{\rm det}=0.5$ rad,

  * •

beam bunch rate $R_{b}$ to deliver the given PoT,

  * •

beam exposure $N_{\rm yr}=1$ year.

The default bunch rate (denoted by $R_{b}^{\star}$) can be calculated from
PoT/bunch in Table 1; for PIP-II we assume 100 MHz for illustration.
Additionally, we impose an energy cut on signal photons, i.e., $E_{\gamma,{\rm
cut}}=100$ MeV, to mitigate the neutron-induced photon backgrounds and to
reflect the reasonable detector capabilities. We find that a negligible number
of accidental photon pairs can pass this hard energy cut. We do not vary the
detector distance but fix it to be $L_{\rm dist}=1$ meter throughout our study
since we are primarily interested in the prompt-decay region.222Strictly
speaking, signal production points differ from event to event, hence $L_{\rm
dist}$ varies. We consider this as an average distance. The thin red solid
curve shows our reference sensitivity reaches expected at the 800-MeV PIP-II.
For comparison purposes, the current constraints compiled in e.g., Refs.
Fortin  _et al._ (2021); Batell  _et al._ (2022) are in the grey and yellow
shaded area.

The remaining four curves compare the sensitivity reaches with different
experimental parameter choices against the reference one, keeping all others
at default values. The magenta solid line is for a 10-times increased beam
exposure. It enables extending the sensitivity reaches toward the bottom and
the higher-mass regions (region IV in FIG. 1) that are sensitive to
statistics. The sensitivity toward the prompt-decay region (region V in FIG.
1), however, does not change since the limit has already been reached. A
similar statement is relevant to the other cases, a 10-times decreased polar-
angular coverage with the blue dot-dashed line, a 100-times increased bunch
rate with the green dashed line, and a 10-times decreased decay volume length
with the orange dotted line. Again for all of them, we lose or gain some
sensitivity in the floor and higher-mass regions (region IV), but their
impacts on the sensitivity in the prompt-decay region (region V) are
negligible.

All these comparisons suggest that sensitivity estimates near the beam-dump
ceiling (below $m_{a}\lesssim 300$ MeV for PIP-II) are robust as predicted
earlier, changing at most $5\sim 10\%$ level below $m_{a}=300$ MeV, as shown
in the inset. More quantitatively speaking, for example, the comparison
between the red and green curves essentially represents the case where the
required number of signal events to determine the sensitivity differs by an
order of magnitude (i.e., a 1,000% change) due to a mis-modeling of
systematics and/or an incorrect background estimation.

Figures 2($b,c$) display our sensitivity estimates at SPS and LHC-dump,
respectively. Unlike PIP-II, more energetic photons would come out of the
target in addition to the neutron-induced photons, such as those from
processes like $K_{L}^{0}\to 3\pi^{0}\to 6\gamma$, due to higher proton beam
energies. Our GEANT4 simulation suggests that the backgrounds from photons
exiting the target are significantly suppressed with $E_{\gamma,{\rm cut}}$
and PoT/bunch in Table 1; more quantitatively, $\sim 4.0\times 10^{8}$ and
$\sim 4.2\times 10^{12}$ accidental photon pairs per year at SPS and LHC-dump,
respectively. Assuming a similar-level suppression factor of $\sim
10^{8}-10^{9}$ as in Ref. Jang  _et al._ (2023) along with posterior cuts
(e.g., invariant mass window) therein, we expect $\sim 4$ and $\sim 42,000$
di-photon backgrounds annually.

Similarly to the PIP-II case, the maximum sensitivity reaches around the beam-
dump ceiling are rather robust and nearly insensitive to beam parameters,
detector geometry, statistics, etc. As pointed out earlier, the impact of the
detector angular coverage is much less pronounced in SPS and the LHC than that
in PIP-II since the signal is more highly forward-directed.

Discussion and conclusions. In this Letter, we presented a study of the
(visibly) decaying signals of new mediators at beam-dump-type experiments,
taking ALPs with couplings to photons for illustration. We clearly showed that
the sensitivity near the beam-dump ceiling, the maximum sensitivity reach that
an experiment can accomplish in the prompt-decay region, is robust and
insensitive to detector geometry, beam specifications, and
background/systematics estimates. Moreover, we provided means to assess
whether the projected sensitivity of an experiment hits the ceiling in Eqs.
(2-4).

Our study further suggests that a compact ``tabletop-sized'' detector is
sufficient to reach the beam-dump ceiling of a given experiment with a
moderate beam exposure. Therefore, multiple, short-term experiments with the
same compact detector system can be performed at different beam facilities,
providing complementary information for probing the parameter space,
especially toward the prompt-decay regime. For example, the solid curves in
FIG. 2($d$) show the sensitivity of the three beam facilities with $\Delta
L_{\rm det}=1$ meter, $\theta_{\rm det}=0.05$ rad, and $N_{\rm yr}=3$ months;
ECAL with just a 10-cm-scale radius could reach, compared to the default
configurations in dotted lines. These examples clearly support the case of
compact, portable experiments that can be performed in different facilities,
complementing each other in expanding reachable parameter space.

## Acknowledgments

For facilitating portions of this research, the authors wish to acknowledge
the Center for Theoretical Underground Physics and Related Areas (CETUP*), the
Institute for Underground Science at Sanford Underground Research Facility
(SURF), and the South Dakota Science and Technology Authority for hospitality
and financial support, as well as for providing a stimulating environment.
This article was supported by the computing resources of the Global Science
Experimental Data Hub Center (GSDC) at the Korea Institute of Science and
Technology Information (KISTI). We thank Wooyoung Jang for the valuable
discussions. The work of DK and HK is supported by the U.S. Department of
Energy Grant DE-SC0010813. The work of JCP is supported by the National
Research Foundation of Korea (NRF) [NRF-2019R1C1C1005073,
NRF-2021R1A4A2001897]. The work of JY is supported by the U.S. Department of
Energy under Grant No. DE-SC0011686.

## References

  * Krasznahorkay  _et al._ (2016) A. J. Krasznahorkay _et al._ , Phys. Rev. Lett. 116, 042501 (2016), arXiv:1504.01527 [nucl-ex] .
  * Krasznahorkay  _et al._ (2019) A. J. Krasznahorkay _et al._ , (2019), arXiv:1910.10459 [nucl-ex] .
  * Krasznahorkay  _et al._ (2021) A. J. Krasznahorkay, M. Csatlós, L. Csige, J. Gulyás, A. Krasznahorkay, B. M. Nyakó, I. Rajta, J. Timár, I. Vajda, and N. J. Sas, Phys. Rev. C 104, 044003 (2021), arXiv:2104.10075 [nucl-ex] .
  * Krasznahorkay  _et al._ (2022) A. J. Krasznahorkay _et al._ , Phys. Rev. C 106, L061601 (2022), arXiv:2209.10795 [nucl-ex] .
  * Krasznahorkay  _et al._ (2023) A. J. Krasznahorkay, A. Krasznahorkay, M. Csatlós, L. Csige, J. Timár, M. Begala, A. Krakó, I. Rajta, and I. Vajda, (2023), arXiv:2308.06473 [nucl-ex] .
  * Bennett  _et al._ (2006) G. W. Bennett _et al._ (Muon g-2), Phys. Rev. D 73, 072003 (2006), arXiv:hep-ex/0602035 .
  * Abi  _et al._ (2021) B. Abi _et al._ (Muon g-2), Phys. Rev. Lett. 126, 141801 (2021), arXiv:2104.03281 [hep-ex] .
  * Aguillard  _et al._ (2023) D. P. Aguillard _et al._ (Muon g-2), Phys. Rev. Lett. 131, 161802 (2023), arXiv:2308.06230 [hep-ex] .
  * Aguilar-Arevalo  _et al._ (2001) A. Aguilar-Arevalo _et al._ (LSND), Phys. Rev. D 64, 112007 (2001), arXiv:hep-ex/0104049 .
  * Aguilar-Arevalo  _et al._ (2009) A. A. Aguilar-Arevalo _et al._ (MiniBooNE), Phys. Rev. Lett. 102, 101802 (2009), arXiv:0812.2243 [hep-ex] .
  * Aguilar-Arevalo  _et al._ (2018) A. A. Aguilar-Arevalo _et al._ (MiniBooNE), Phys. Rev. Lett. 121, 221801 (2018), arXiv:1805.12028 [hep-ex] .
  * Aguilar-Arevalo  _et al._ (2021) A. A. Aguilar-Arevalo _et al._ (MiniBooNE), Phys. Rev. D 103, 052002 (2021), arXiv:2006.16883 [hep-ex] .
  * Batell  _et al._ (2022) B. Batell _et al._ , in  _Snowmass 2021_ (2022) arXiv:2207.06898 [hep-ph] .
  * Ilten  _et al._ (2018) P. Ilten, Y. Soreq, M. Williams, and W. Xue, JHEP 06, 004 (2018), arXiv:1801.04847 [hep-ph] .
  * Bauer  _et al._ (2018) M. Bauer, P. Foldenauer, and J. Jaeckel, JHEP 07, 094 (2018), arXiv:1803.05466 [hep-ph] .
  * Fabbrichesi  _et al._ (2020) M. Fabbrichesi, E. Gabrielli, and G. Lanfranchi,  (2020), 10.1007/978-3-030-62519-1, arXiv:2005.01515 [hep-ph] .
  * Fortin  _et al._ (2021) J.-F. Fortin, H.-K. Guo, S. P. Harris, D. Kim, K. Sinha, and C. Sun, Int. J. Mod. Phys. D 30, 2130002 (2021), arXiv:2102.12503 [hep-ph] .
  * Jang  _et al._ (2023) W. Jang, D. Kim, K. Kong, Y. Kwon, J.-C. Park, M. S. Ryu, S. Shin, R. G. Van de Water, U.-K. Yang, and J. Yu, Phys. Rev. D 107, L031901 (2023), arXiv:2207.02223 [hep-ph] .
  * Note (1) From now on, we will use beam target and dump interchangeably as we will show that the target width does not affect our results.
  * Dutta  _et al._ (2023) B. Dutta, D. Kim, and H. Kim, (2023), arXiv:2305.16383 [hep-ph] .
  * Ainsworth  _et al._ (2021) R. Ainsworth _et al._ , (2021), arXiv:2106.02133 [physics.acc-ph] .
  * Ahdida  _et al._ (2020) C. C. Ahdida _et al._ ,  _SPS Beam Dump Facility - Comprehensive Design Study_, edited by M. Calviani, B. Goddard, R. Jacobsson, and M. Lamont, CERN Yellow Reports: Monographs, Vol. 2/2020 (2020) arXiv:1912.06356 [physics.acc-ph] .
  * Maestre  _et al._ (2021) J. Maestre _et al._ , JINST 16, P11019 (2021), arXiv:2110.08783 [physics.acc-ph] .
  * Apyan  _et al._ (2022) A. Apyan _et al._ , in  _Snowmass 2021_ (2022) arXiv:2203.08322 [hep-ex] .
  * Cortina Gil  _et al._ (2017) E. Cortina Gil _et al._ (NA62), JINST 12, P05025 (2017), arXiv:1703.08501 [physics.ins-det] .
  * Alekhin  _et al._ (2016) S. Alekhin _et al._ , Rept. Prog. Phys. 79, 124201 (2016), arXiv:1504.04855 [hep-ph] .
  * Primakoff (1951) H. Primakoff, Phys. Rev. 81, 899 (1951).
  * Agostinelli  _et al._ (2003) S. Agostinelli _et al._ (GEANT4), Nucl. Instrum. Meth. A 506, 250 (2003).
  * Note (2) Strictly speaking, signal production points differ from event to event, hence $L_{\rm dist}$ varies. We consider this as an average distance.