\section{Introduction}

\begin{figure}[!t]
\centering
\includegraphics[width = 3.2in]{introNew}
\vspace{-10pt}
\caption{Images captured few minutes before Boston Marathon Bombing, 2013, of suspect Dzhokhar Tsarnaev (circled). The resolution of the circled image is less than $24\times24$, which is interpolated to ($96\times96$).}
\vspace{-15pt}
\label{intro}
\end{figure}

Group images are often captured from a distance, in order to capture multiple people in the image. In such cases, the resolution of each face image is relatively smaller, thereby resulting in errors during automated tagging. Similarly, in surveillance and monitoring applications, cameras are often designed to cover the maximum field of view, this often limits the size of face images captured, especially for individuals at a distance. If we use these images to match against high resolution images, e.g., profile images on social media or mugshot images captured by law enforcement, then resolution gap between the two may lead to incorrect results. This task of matching a low resolution input image against a database of high resolution images is referred to as cross resolution face recognition and it is a challenging covariate of face recognition with widespread applications.

Several researchers have shown that the performance of state-of-the-art (SOTA) algorithms reduces while matching cross-resolution face images \cite{himanshu, wang16CVPR, Wang2013}. In order to overcome this limitation, an intuitive approach is to generate a high resolution image for the given low resolution input, which can be provided as input to the face recognition engine. Figure \ref{intro} shows a sample real world image captured before the Boston Bombing (2013). Since the person of interest is at a distance, the face captured is thus of low resolution. Upon performing bicubic interpolation to obtain a high resolution image, results in an image suffering from blur and poor quality.
With the ultimate aim of high recognition performance, the generated high resolution image should have good quality while preserving the identity of the subject. As elaborated in the next subsection, while there exist multiple synthesis or super resolution techniques, we hypothesize that utilizing a (domain) face-specific, recognition-oriented model for face synthesis should result in improved recognition performance, especially for close-set recognition scenarios. To this effect, this work presents a novel domain specific identity aware \textit{Synthesis via Deep Sparse Coding} algorithm for synthesizing a high resolution face image from a given low resolution input image.

\subsection{Literature Review}
In literature, different techniques have been proposed to address the problem of cross resolution face recognition. These can broadly be divided into transformation based techniques and non-transformation based techniques. Transformation based techniques address the resolution difference between images by explicitly introducing a transformation function either at the image or at the feature level. Non-transformation techniques propose to learn/extract resolution invariant features or classifiers, in order to address the resolution variations \cite{himanshu, wang16CVPR}. In 2013, Wang \textit{et al.} \cite{Wang2013} present an exhaustive review of the proposed techniques for addressing cross resolution face recognition.

Peleg and Elad \cite{peleg} propose a statistical model that uses Minimum Mean Square Error estimator on high and low resolution image pair patches for prediction. Lam \cite{jian2015} propose a Singular Value Decomposition based approach for super resolving low resolution face images. Researchers have also explored the domain of representation learning to address the problem of cross resolution face recognition. Yang \textit{et al.} \cite{yang} propose learning dictionaries for low and high resolution image patches jointly followed by learning a mapping between the two. Yang \textit{et al.} \cite{icb} propose a Sparse Representation-based Classification approach in which the face recognition and hallucination constraints are solved simultaneously. Gu \textit{et al.} \cite{gu_iccv15} propose convolutional sparse coding where an image is divided into patches and filters are learned to decompose a low resolution image into features. A mapping is learned to predict high resolution feature maps from the low resolution features. Mundunuri and Biswas \cite{mundunuri16} propose a multi-dimensional scaling and stereo cost technique to learn a common transformation matrix for addressing the resolution variations.

A parallel area of research is that of super-resolution, where research has focused on obtaining a high resolution image from a given low resolution image, with the objective of maintaining/improving the visual quality of the input \cite{baker2000, bayesianSR, wang14Rev, scdl}. There has been significant advancement in the field of super-resolution over the past several years including recent representation learning architectures \cite{pixel17Iccv, srcnn, fsrcnn, ledig17Cvpr, tong17Iccv} being proposed for the same. It is important to note that while such techniques can be utilized for addressing cross resolution face recognition, however, they are often not explicitly trained for face images, or for providing recognition-oriented results.

\subsection{Research Contributions}
 This research focuses on cross resolution face recognition by proposing a recognition-oriented image synthesis algorithm, capable of handling large magnification factors. We propose a deep sparse representation based transfer learning approach termed as Synthesis via Deep Sparse Representation (SDSR). The proposed identity aware synthesis algorithm can be incorporated as a pre-processing module prior to any existing face recognition engine to enhance the resolution of a given low resolution input. In order to ensure recognition-oriented synthesis, the proposed model is trained using a gallery database having a single image per subject. The results are demonstrated with four databases and the effectiveness is evaluated in terms of both no-reference image quality measure of the synthesized images and face identification accuracies with existing face recognition models.

\section{Synthesis via Deep Sparse Representation}
\label{algo}
Dictionary Learning algorithms have an inherent property of representing a given sample as a sparse combination of it's basis functions \cite{doubleSparsity}. This property is utilized in the proposed SDSR algorithm to synthesize a high resolution image from a given low resolution input. The proposed model learns a transformation between the representations of low and high resolution images. That is, instead of interpolating the pixel values, this work focuses on interpolating a more abstract representation. Further, motivated by the abstraction capabilities of deep learning, we propose to learn the transformation from deeper levels of representation. Unlike traditional dictionary learning algorithms, we propose to learn the transformation at deeper levels of representation. This leads to the key contribution of this work: \textit{Synthesis via Deep Sparse Representation (SDSR)}, a transfer learning approach for synthesizing a high resolution image for a given low resolution input.

\subsection{Preliminaries}
Let $\mathbf{X = [x^\textit{1}| x^\textit{2}| ... |x^\textit{n}]}$ be the input training data with $n$ samples. Dictionary learning algorithms learn a \textit{dictionary} ($\mathbf{D}$) and \textit{sparse representations} ($\mathbf{A}$) using data ($\mathbf{X}$). The objective function of dictionary learning is written as:
\begin{equation} \label{eqDict}
\min_{\textit{$\mathbf{D, A}$}}  \frac{1}{n} \sum \limits_{i=1}^{n} \Big( \frac{1}{2} \left \| \mathbf{x^{\textit{i}} - D \boldsymbol{\alpha^\textit{i}}} \right \|_{F}^{2} + \lambda \left\| \boldsymbol{\alpha^\textit{i}}\right\|_1 \Big)
\end{equation}
\noindent where, $\mathbf{A = \boldsymbol{[\alpha^\textit{1}| \alpha^\textit{2}| .... |\alpha^\textit{n}]}}$ are the sparse codes, $\left\| \cdot \right\|_1$ represents $\ell_1$-norm, and $\lambda$ is the regularizing constant that controls how much weight is given to induce sparsity in the representations. In Eq. \ref{eqDict}, the first term minimizes the reconstruction error of the training samples, and the second term is a regularization term on the sparse codes.

In literature, researchers have proposed extending a single level dictionary to a multi-level dictionary to learn multiple levels of representations of the given data \cite{sparseFilt, deepDict, multiLevel}.
A $k-$level deep dictionary learns $k$ dictionaries $\mathbf{D = \{D^\textit{1}, ..., D^\textit{k}\}}$ and sparse coefficients $\mathbf{A = \{A^\textit{1}, ..., A^\textit{k}\}}$ for a given input $\mathbf{X}$.
\begin{equation} \label{eqDeepDict}
\min_{\textit{$\mathbf{D, A}$}} \  \frac{1}{n} \sum \limits_{i=1}^{n}\Big( \frac{1}{2} \left \| \mathbf{x^\textit{i} - D^\textit{1}...D^\textit{k} \boldsymbol{\alpha^\textit{k,i}}} \right \|_{F}^{2} + \lambda \left\| \boldsymbol{\alpha^\textit{k,i}}\right\|_1 \Big)
\end{equation}
The architecture of deep dictionary is inspired from the deep learning techniques where deeper layers of feature learning enhance the level of abstraction learned by the network, thereby learning meaningful latent variables.

\begin{figure*}
\centering
\includegraphics[width= 6.9in]{combined}
\vspace{-5pt}
\caption{Synthesis via Deep Sparse Representation algorithm for 2-level deep dictionary. (a) refers to the training of the model, while (b) illustrates the high resolution synthesis of a low resolution input. }
\vspace{-10pt}
\label{algo}
\end{figure*}

\subsection{SDSR Algorithm}
In real world scenarios of surveillance or image tagging, the task is to match the low resolution test images (probe) to the database of high resolution images known as \textit{gallery images}. Without loss of generality, we assume that the target comprises of high resolution gallery images while the source domain consists of low resolution images. In the proposed model, for low resolution face images $\mathbf{X}_{l}$, and high resolution face images $\mathbf{X}_{h}$, $k$ level deep dictionaries are learned in both source ($\mathbf{G_{L} = \{G_\textit{l}^\textit{1}, ...,  G_\textit{l}^\textit{k}\}}$) and target domain ($\mathbf{G_{H} = \{G_\textit{h}^\textit{1}, ..., G_\textit{h}^\textit{k}}\}$). It is important to note that the dictionaries are generated using the pre-acquired gallery images. Corresponding sparse representations, $\mathbf{A_{L} = \{A_\textit{l}^\textit{1}, ...,  A_\textit{l}^\textit{k}\}}$ and $\mathbf{A_{H} = \{A_\textit{h}^\textit{1}, ...,  A_\textit{h}^\textit{k}\}}$ are also learned for all $k$ levels, where $\boldsymbol{\mathbf{A_\textit{h}^\textit{k}} = [\alpha_\textit{h}^\textit{k,1}| \alpha_\textit{h}^\textit{k,2}| ... |\alpha_\textit{h}^\textit{k,n}]}$ are the representations learnt corresponding to the high resolution deep dictionary and $\boldsymbol{\mathbf{A_\textit{l}^\textit{k}} = [\alpha_\textit{l}^\textit{k,1}| \alpha_\textit{l}^\textit{k,2}| ... |\alpha_\textit{l}^\textit{k,n}]}$ are the representations learnt from the $k^{th}$ level dictionary for the low resolution images. The proposed algorithm learns a transformation, $\mathbf{M}$, between $\mathbf{A^\textit{k}_\textit{h}}$ and $\mathbf{A^\textit{k}_\textit{l}}$. The optimization formulation for Synthesis via Deep Sparse Representation (SDSR), a $k$-level deep dictionary is written as:

\begin{equation} \label{eqProposed}
\begin{split}
\min_{\textit{$\substack{ \mathbf{G_{H}, A_{H},} \\ \mathbf{G_{L}, A_{L}, M} }$}} &  \frac{1}{n} \sum \limits_{i=1}^{n} \Big( \frac{1}{2} \left \| \mathbf{x_\textit{h}^\textit{i} - G_\textit{h}^\textit{1} ... G_\textit{h}^\textit{k} \boldsymbol{\alpha_\textit{h}^\textit{k,i} }} \right \|_{F}^\textit{2} + \sum \limits_{j = 1} ^{k} (\lambda_j \left\| \boldsymbol{\alpha_h^\textit{j,i}}\right\|_1)\\
& + \frac{1}{2} \left \| \mathbf{x_\textit{l}^\textit{i} - G_\textit{l}^\textit{1} ... G_\textit{l}^\textit{k} \boldsymbol{\alpha_\textit{l}^\textit{k,i}} }\right \|_{F}^{2} + \sum \limits_{j = 1} ^{k} (\lambda_j \left\| \boldsymbol{\alpha_l^\textit{j,i}}\right\|_1)\\
& + \lambda_M  \left\| \mathbf{\boldsymbol{\alpha_\textit{h}^\textit{k,i}} - M\boldsymbol{\alpha_\textit{l}^\textit{k,i}}} \right\|_F^2 \Big)
\end{split}
\end{equation}
where, $\lambda_j$ are regularization parameters which control the amount of sparsity in the learned representations of the $j^{th}$ layer, while $\lambda_M$ is the regularization constant for learning the transformation function. $\mathbf{G_{H}}$ and $\mathbf{G_{L}}$ correspond to the deep dictionaries learned for the high and low resolution gallery images, respectively. The SDSR algorithm learns multiple levels of dictionaries and corresponding representations for low and high resolution face images, along with a transformation between the features learned at the deepest layer.

\subsubsection{Training SDSR Algorithm}
Without loss of generality, training of the proposed SDSR algorithm is explained with $k = 2$ (shown in Figure \ref{algo}). For a two level deep dictionary, Eq. \ref{eqProposed} can be written as:
\begin{equation} \label{eqComplete}
\begin{gathered}
\min_{\textit{$\substack{ \mathbf{G_{H}, G_{L}} \\ \mathbf{A_{H}, A_{L}, M} }$}}   \frac{1}{n} \sum \limits_{i=1}^{n} \Big( \frac{1}{2} \left \| \mathbf{x_\textit{h}^\textit{i} - G_\textit{h}^\textit{1}G_\textit{h}^\textit{2} \boldsymbol{\alpha_\textit{h}^\textit{2,i}}} \right \|_{F}^\textit{2} + \lambda_1 \left\| \boldsymbol{\alpha_\textit{h}^\textit{1,i }}\right\|_1 \\
+ \lambda_2 \left\| \boldsymbol{\alpha_\textit{h}^\textit{2,i }}\right\|_1 + \frac{1}{2} \left \| \mathbf{x_\textit{l}^\textit{i} - G_\textit{l}^\textit{1}G_\textit{l}^\textit{2} \boldsymbol{\alpha_\textit{l}^\textit{2,i}} }\right \|_{F}^\textit{2} + \lambda_1 \left\| \boldsymbol{\alpha_\textit{l}^\textit{1,i }}\right\|_1 \\
+ \lambda_2 \left\| \boldsymbol{\alpha_\textit{l}^\textit{2,i }}\right\|_1 + \lambda_M  \left\| \mathbf{\boldsymbol{\alpha_\textit{h}^\textit{2,i} - \mathbf{M}\alpha_\textit{l}^\textit{2,i}}} \right\|_F^2 \Big)
\end{gathered}
\end{equation}
Since the number of variables in Eq. \ref{eqComplete} is large (even more for deeper dictionaries), directly solving the optimization problem may provide incorrect estimates and lead to overfitting. Therefore, greedy layer by layer training is applied. It is important to note that since there is a $l_{1}$-norm regularizer on the coefficients of the first and the second layer, the dictionaries $\mathbf{G}_h^1$ and $\mathbf{G}_h^2$ cannot be collapsed into one dictionary. In order to learn the estimates, Eq. \ref{eqComplete} is split into learning the first level representation, second level representation, and the transformation. From Eq. \ref{eqDeepDict}, the optimization function for two level deep dictionary is as follows:
\begin{equation} \label{eqTarget}
\min_{\textit{$\substack{\mathbf{G^\textit{1},D^\textit{2},} \\ \mathbf{A^\textit{1}, A^\textit{2}}}$}}  \frac{1}{n} \sum \limits_{i=1}^{n} \Big( \frac{1}{2} \left \| \mathbf{x^\textit{i} - G^\textit{1}G^\textit{2} \boldsymbol{\alpha^\textit{2,i}} }\right \|_{F}^\textit{2} + \lambda_1 \left\| \boldsymbol{\alpha^\textit{1,i}} \right\|_1 +  \lambda_2 \left\| \boldsymbol{\alpha^\textit{2,i}} \right\|_1 \Big)
\end{equation}
\indent Assuming an intermediate variable, $\boldsymbol{\alpha^\textit{1,i} = }\mathbf{G^\textit{2}\boldsymbol{\alpha^\textit{2,i}}}$ such that $\mathbf{A^\textit{1} = \boldsymbol{[\alpha^\textit{1,1}| \alpha^\textit{1,2}| ... |\alpha^\textit{1,n}]}}$, the above equation can be modeled as a step-wise optimization of the following two equations:
\begin{equation} \label{eqTargetGreedyFirst}
\min_{\textit{$\mathbf{G^\textit{1}, A^\textit{1}}$}}  \frac{1}{n} \sum \limits_{i=1}^{n} \Big( \frac{1}{2} \left \| \mathbf{x^\textit{i} - G^\textit{1}\boldsymbol{\alpha^\textit{1,i} }}\right \|_{F}^{2} + \lambda_1 \left\| \boldsymbol{\alpha^\textit{1,i}} \right\|_1 \Big)
\end{equation}
\begin{equation} \label{eqTargetGreedySecond}
\min_{\textit{$\mathbf{G^\textit{2}, A^\textit{2}}$}}  \frac{1}{n} \sum \limits_{i=1}^{n} \Big( \frac{1}{2} \left \|\boldsymbol{\alpha^\textit{1,i}} - \mathbf{G^\textit{2} \boldsymbol{\alpha^\textit{2,i}} }\right \|_{F}^{2} + \lambda_2 \left\| \boldsymbol{\alpha^\textit{2,i} }\right\|_1 \Big)
\end{equation}
\indent A deep dictionary of two levels (Eq. \ref{eqTarget}) requires two steps for learning (Eq. \ref{eqTargetGreedyFirst}, \ref{eqTargetGreedySecond}). Upon extending the formulation to $k$ level deep dictionary, it would require exactly $k$ steps for optimization. The proposed SDSR algorithm (Eq. \ref{eqProposed}) builds upon the above and utilizes $k+1$ steps based greedy layer-wise learning for a $k$ level deep dictionary. $k$ steps are for learning representations using the deep dictionary architecture and the $k+1^{th}$ step is for learning the transformation between the final representations. Therefore, Eq. \ref{eqComplete} is solved using an independent three step approach:
\textbf{(i)} learn first level source (low resolution) and target (high resolution) domain dictionaries,
\textbf{(ii)} learn second level low and high resolution image dictionaries, and
\textbf{(iii)} learn a transformation between the final representations.

Using the concept in Eq. \ref{eqTarget} - \ref{eqTargetGreedySecond}, in the \textbf{first step}, two separate level-1 (i.e. $k=1$) dictionaries are learned from the given input data for the low resolution ($\mathbf{G^\textit{1}_\textit{l}}$) and high resolution ($\mathbf{G_\textit{h}^\textit{1}}$) face images independently. Given the training data consisting of low ($\mathbf{X_\textit{l}}$) and high ($\mathbf{X_\textit{h}}$) resolution face images, the following minimization is applied for the two domains respectively:
\begin{equation} \label{eqDictSource}
\min_{\textit{$\mathbf{G_\textit{l}^\textit{1},A_\textit{l}^\textit{1}}$}} \frac{1}{n} \sum \limits_{i=1}^{n}  \frac{1}{2} \left \| \mathbf{x_\textit{l}^\textit{i} - G_\textit{l}^\textit{1} \boldsymbol{\alpha_\textit{l}^\textit{1,i} }} \right \|_{2}^{2}  +  \lambda_1 \left\| \boldsymbol{\alpha_\textit{l}^\textit{1,i}} \right\|_1
\end{equation}
\begin{equation} \label{eqDictTarget}
\min_{\textit{$\mathbf{G_\textit{h}^\textit{1},A_\textit{h}^\textit{1}}$}} \frac{1}{n} \sum \limits_{i=1}^{n}  \frac{1}{2} \left \|\mathbf{x_\textit{h}^\textit{i} - G_\textit{h}^\textit{1} \boldsymbol{\alpha_\textit{h}^\textit{1,i}}} \right \|_{2}^{2}  +  \lambda_1 \left\| \boldsymbol{\alpha_\textit{h}^\textit{1,i}} \right\|_1
\end{equation}
\noindent here, $\mathbf{A_\textit{l}^\textit{1} = \boldsymbol{[\alpha_\textit{l}^\textit{1,1}| \alpha_\textit{l}^\textit{1,2}| ... |\alpha_\textit{l}^\textit{1,n}]}}$ and $\mathbf{A_\textit{h}^\textit{1} = \boldsymbol{[\alpha_\textit{h}^\textit{1,1}| \alpha_\textit{h}^\textit{1,2}| ... |\alpha_\textit{h}^\textit{1,n}]}}$ refer to the level-1 sparse codes learned for the low and high resolution images respectively. Each of the above two equations can be optimized independently using an alternating minimization dictionary learning technique over the dictionary $\mathbf{G}^1$ and representation $\mathbf{A}^1$ \cite{dictLearning}. After this step, $\mathbf{G_\textit{h}^\textit{1}, G_\textit{l}^\textit{1}}$ (dictionaries) and $\mathbf{A_\textit{h}^\textit{1}, A_\textit{l}^\textit{1}}$ (representations) are obtained for the two varying resolution data.

In the \textbf{second step}, a deep dictionary is created by learning the second level dictionaries ($\mathbf{G_\textit{l}^\textit{2}}, \mathbf{G_\textit{h}^\textit{2}}$) using the representations obtained from the first level ($\mathbf{A_\textit{h}^\textit{1}}$ and $\mathbf{A_\textit{l}^\textit{1}}$). That is, two separate dictionaries, one for low resolution images and one for high resolution images are learned using the representations obtained at the first level as input features. The equations for this step can be written as follows:
\begin{equation} \label{eqAlphaDictSource}
\min_{\textit{$\mathbf{G_\textit{l}^\textit{2} ,\boldsymbol{A_\textit{l}^\textit{2}}}$}} \frac{1}{n} \sum \limits_{i=1}^{n}  \frac{1}{2} \left \|\boldsymbol{\alpha_\textit{l}^\textit{1,i}} - \mathbf{G_\textit{l}^\textit{2} \boldsymbol{\alpha_\textit{l}^\textit{2,i}}} \right \|_{2}^{2}  +  \lambda_2 \left\| \boldsymbol{\alpha_\textit{l}^\textit{2,i}} \right\|_1
\end{equation}
\begin{equation} \label{eqAlphaDictTarget}
\min_{\textit{$\mathbf{G_\textit{h}^\textit{2},\boldsymbol{A_\textit{h}^\textit{2}}}$}} \frac{1}{n} \sum \limits_{i=1}^{n}  \frac{1}{2} \left \| \boldsymbol{\alpha_\textit{h}^\textit{1,i}} - \mathbf{G_\textit{h}^\textit{2}  \boldsymbol{\alpha_\textit{h}^\textit{2,i}}} \right \|_{2}^{2}  +  \lambda_2 \left\| \boldsymbol{\alpha_\textit{h}^\textit{2,i}} \right\|_1
\end{equation}
\noindent here, $\mathbf{A_\textit{l}^\textit{2} = \boldsymbol{[\alpha_\textit{l}^\textit{2,1}| \alpha_\textit{l}^\textit{2,2}| ... |\alpha_\textit{l}^\textit{2,n}]}}$ is the final representation obtained for the low resolution images and $\mathbf{A_\textit{h}^\textit{2} = \boldsymbol{[\alpha_\textit{h}^\textit{2,1}| \alpha_\textit{h}^\textit{2,2}| ... |\alpha_\textit{h}^\textit{2,n}]}}$ refers to the representation obtained for the high resolution images. Similar to the previous step, the equations can be solved independently using alternating minimization over the dictionary and representations. After this step, $\mathbf{G_\textit{l}^\textit{2}, G_\textit{h}^\textit{2}, A_\textit{l}^\textit{2}}$ and $\mathbf{A_\textit{h}^\textit{2}}$ are obtained.

In order to synthesize from one resolution to another, the \textbf{third step} of the algorithm involves learning a transformation between the deep representations of the two resolutions (i.e. $\mathbf{A_\textit{l}^\textit{2}}$ and $\mathbf{A_\textit{h}^\textit{2}}$). The following minimization is solved to obtain a transformation $\mathbf{M}$.
\begin{equation} \label{eqMapping}
\min_{\textit{$\mathbf{M}$}} \frac{1}{2} \left \|\mathbf{A_\textit{h}^\textit{2} - MA_\textit{l}^\textit{2}}\right \|_{F}^{2}
\end{equation}
The above equation is a least square problem having a closed form solution. After training, the dictionaries ($\mathbf{G_\textit{l}^1, G_\textit{h}^1, G_\textit{l}^2, G_\textit{h}^2}$) and the transformation function ($\mathbf{M}$) are obtained which are then used at test time.
\begin{table*}
\centering
\small
\caption{Summarizing the characteristics of the training and testing partitions of the databases used in experiments.}
\vspace{-10pt}
\label{tab:dbase}
\begin{tabular}{|l|m{4em}|m{4em}|m{4em}|m{4em}|m{6em}|m{11.5em}|}
\hline
\multirow{2}{*}{\textbf{Dataset}} & \textbf{Training Subjects} & \textbf{Training Images} &\textbf{Testing Subjects} & \textbf{Testing Images} & \textbf{Gallery Resolution}  & \multirow{2}{*}{\textbf{Probe Resolutions}}  \\ \hline

\textbf{CMU Multi-PIE \cite{mpie}} & 100 & 200 & 237 & 474 & \multirow{5}{*}{$96\times96$} & \\\cline{1-5}
\textbf{CAS-PEAL \cite{caspeal}} &500 & 659 & 540 & 705 & &\multirow{2}{*}{$8\times8$, $16\times16$, $24\times24$,}  \\\cline{1-5}
\textbf{Real World Scenarios \cite{himanshu}} & - & - & 1207 & 1222 &  & \\\cline{1-5} \cline{7-7}
\textbf{SCface \cite{scface}} & 50 & 300 & 80 & 480 & & $24\times24$, $32\times32$, $48\times48$ \\ \hline
\end{tabular}
\vspace{-5pt}
\end{table*}

\begin{table*}[]
\centering
\small
\caption{Rank-1 identification accuracies (\%) obtained using Verilook (COTS-I) for cross resolution face recognition. The target resolution is $96\times96$. The algorithms which do not support the required magnification factor are presented as $'-'$.}
\vspace{-10pt}
\label{verilookResults}
\begin{tabular}{|m{1.5em}|m{5em}|m{3.7em}|m{3.5em}|m{3.5em}|m{3.5em}|m{3.5em}|m{3.5em}|m{3.5em}|m{3.5em}|m{4em}|}
\hline
\multirow{2}{*}{} & \textbf{Probe Resolution} & \textbf{Original Image} & \textbf{Bicubic Interp.} & \textbf{Dong \textit{et al.} \cite{fsrcnn}} & \textbf{Kim \textit{et al.} \cite{kwan}} & \textbf{Gu \textit{et al.} \cite{gu_iccv15}} & \textbf{Dong \textit{et al.} \cite{srcnn}} &  \textbf{Peleg \textit{et al.} \cite{peleg}} & \textbf{Yang \textit{et al.} \cite{yang}} & \textbf{Proposed SDSR} \\
\hhline {|=|=|=|=|=|=|=|=|=|=|=|}

\multirow{5}{*}{\rotatebox[origin=c]{90}{\parbox[c]{2cm}{\centering \textbf{CMU MultiPIE}}} } &
8$\times$8 & 0.0$\pm$0.0 & 0.1$\pm$0.0 & - & - & - & - & - & - & \textbf{82.6$\pm$1.5} \\ \cline{2-11}
& 16$\times$16 & 0.0$\pm$0.0 & 1.1$\pm$0.1 & - & - & - & - & - & - & \textbf{91.1$\pm$1.3} \\ \cline{2-11}
& 24$\times$24 & 1.2$\pm$0.4 & 3.1$\pm$0.6 & 2.0$\pm$3.5 & 4.1$\pm$1.0 & 4.3$\pm$1.0 &  4.2$\pm$0.6 & - & - & \textbf{91.8$\pm$1.8} \\ \cline{2-11}
 & 32$\times$32 & 3.4$\pm$0.6 & 16.9$\pm$1.3 & 9.7$\pm$1.1& 17.5$\pm$1.1& 15.4$\pm$1.1 & 6.9$\pm$0.2 & 8.3$\pm$0.9 & - & \textbf{91.9$\pm$1.7} \\ \cline{2-11}
& 48$\times$48 & 91.9$\pm$1.1 & 95.8$\pm$0.4 & 85.8$\pm$0.7 & \textbf{96.2$\pm$0.6} & 93.1$\pm$0.9 & 95.5$\pm$1.1 & 92.8$\pm$0.4 & 94.0$\pm$0.6  & 91.5$\pm$1.5 \\
\hhline {|=|=|=|=|=|=|=|=|=|=|=|}

\multirow{5}{*}{\begin{turn}{90}\textbf{CAS-PEAL}\end{turn}} &
8$\times$8 & 0.0$\pm$0.0 & 0.0$\pm$0.0 & - & - & - & - & - & - & \textbf{92.8$\pm$0.7} \\ \cline{2-11}
& 16$\times$16 & 0.0$\pm$0.0 & 0.2$\pm$0.3 & - & - & - & - & - & - & \textbf{94.4$\pm$1.1} \\ \cline{2-11}
& 24$\times$24 & 0.4$\pm$0.6 & 14.9$\pm$1.7 & 0.4$\pm$0.2 & 2.3$\pm$0.8 & 1.9$\pm$0.7 & 2.5$\pm$0.7 & - & - & \textbf{95.3$\pm$1.4} \\ \cline{2-11}
& 32$\times$32 & 3.7$\pm$0.7 & 76.5$\pm$1.8 & 5.4$\pm$1.2 & 11.8$\pm$1.1 & 8.1$\pm$2.3 & 2.1$\pm$0.7 & 3.1$\pm$1.6 & - & \textbf{95.6$\pm$1.1} \\ \cline{2-11}
& 48$\times$48 & 63.4$\pm$1.7 & 90.8$\pm$1.5 & 46.5$\pm$2.5 & 75.8$\pm$2.3 & 77.7$\pm$2.1 & 72.0$\pm$0.7 & 74.0$\pm$2.6 & 73.3$\pm$3.3 & \textbf{95.4$\pm$1.5} \\ \cline{2-11}
\hhline {|=|=|=|=|=|=|=|=|=|=|=|}

\multirow{3}{*}{\begin{turn}{90}\textbf{SCface}\end{turn}} &
24$\times$24 & 1.1$\pm$0.2 & 0.8$\pm$0.1& 0.4$\pm$0.2 & 0.4$\pm$0.2 & 1.5$\pm$0.3 & 1.3$\pm$0.3 & - & - & \textbf{14.7$\pm$3.3} \\ \cline{2-11}
& 32$\times$32 & 1.8$\pm$0.5 & 2.5$\pm$0.3 & 2.2$\pm$0.4& 2.0$\pm$0.0 & 2.3$\pm$0.3 & 0.7$\pm$0.3 & 1.8$\pm$0.5 & - & \textbf{15.6$\pm$1.3} \\ \cline{2-11}
& 48$\times$48 & 6.5$\pm$0.6 & 9.5$\pm$1.9 & 6.9$\pm$0.6& 6.7$\pm$1.2 & 7.7$\pm$0.6 & 7.5$\pm$1.3 & 7.3$\pm$0.9 & 6.8$\pm$0.7 & \textbf{18.5$\pm$2.6} \\ \hline
\end{tabular}
\end{table*}

\vspace{6pt}
\subsubsection{Testing: Synthesizing High Resolution Face Image from Low Resolution Image}
During testing, a low resolution test image, $\mathbf{x_\textit{l}^\textit{test}}$, is input to the algorithm.
Using the trained gallery based dictionaries, $\mathbf{G_\textit{l}^\textit{1}}$ and $\mathbf{G_\textit{l}^\textit{2}}$, first and second level representations ($\boldsymbol{\alpha_\textit{l}^\textit{1,test}, \alpha_\textit{l}^\textit{2,test}}$) are obtained for the given image:
\begin{equation} \label{eqAlphaSource}
\mathbf{x_\textit{l}^\textit{test} = G_\textit{l}^\textit{1}\boldsymbol{\alpha_\textit{l}^\textit{1,test}}}; \  \boldsymbol{\alpha_\textit{l}^\textit{1,test}} = \mathbf{G_\textit{l}^\textit{2}\boldsymbol{\alpha_\textit{l}^\textit{2,test}}}
\end{equation}
The transformation function, $\mathbf{M}$, learned in Eq. \ref{eqMapping}, is then used to obtain the second level high resolution representation ($\boldsymbol{\alpha_\textit{h}^\textit{2,test}}$).
\begin{equation} \label{eqMappedAlphaAlpha}
\mathbf{\boldsymbol{\alpha_\textit{h}^\textit{2,test}} = M\boldsymbol{\alpha_\textit{l}^\textit{2,test}}}
\end{equation}
Using Eq. \ref{eqDictTarget} and Eq. \ref{eqAlphaDictTarget} and the second level representation for the given image in the target domain, a \textit{synthesized} output of the given image is obtained. First $\boldsymbol{\alpha_\textit{h}^\textit{1,test}}$ is calculated with the help of $\mathbf{G_\textit{h}^\textit{2}}$ and then $\mathbf{x_\textit{h}^\textit{test}}$ is obtained using $\mathbf{G_\textit{h}^\textit{1}}$, which is the synthesized image in the target domain.
\begin{equation} \label{eqAlphaTarget}
\boldsymbol{\alpha_\textit{h}^\textit{1,test}} = \mathbf{G_\textit{h}^2\boldsymbol{\alpha_\textit{h}^\textit{2,test}}}; \ \mathbf{x_\textit{h}^\textit{test} = G_\textit{h}^1\boldsymbol{\alpha_\textit{h}^\textit{1,test}}}
\end{equation}
It is important to note that the synthesized high resolution image is a sparse combination of the basis functions of the learned high resolution dictionary. In order to obtain a good quality, identity-preserving high resolution synthesis, the dictionary is trained with the pre-acquired high resolution database. This ensures that the basis functions of the trained dictionaries span the latent space of the images. As will be demonstrated via experiments as well, a key highlight of this algorithm is to learn good quality, representative dictionaries with a single sample per subject as well. The high resolution synthesized output image $\mathbf{x_\textit{h}^\textit{test}}$  can then be used by any face identification engine for recognition.

\section{Databases and Experimental Protocol}
\label{sec:dbase}

The effectiveness of the proposed SDSR algorithm is demonstrated by evaluating the face recognition performance with original and synthesized images. Two commercial-off-the-shelf face recognition systems (COTS), Verilook (COTS-I) \cite{verilook} and Luxand (COTS-II) \cite{luxand} are used on four different face databases. For Verilook, the face quality and confidence thresholds are set to minimum, in order to reduce enrollment errors. The performance of the proposed algorithm is compared with six recently proposed super-resolution and synthesis techniques by Kim \textit{et al.} \cite{kwan}\footnote{https://people.mpi-inf.mpg.de/~kkim/supres/supres.htm} (kernel ridge regression), Peleg \textit{et al.} \cite{peleg}\footnote{http://www.cs.technion.ac.il/\~elad/software/} (sparse representation based statistical prediction model), Gu \textit{et al.} \cite{gu_iccv15}\footnote{http://www4.comp.polyu.edu.hk/~cslzhang/} (convolutional sparse coding), Yang \textit{et al.} \cite{yang}\footnote{http://www.ifp.illinois.edu/\~jyang29/} (dictionary learning), Dong \textit{et al.} \cite{srcnn}\footnote{http://mmlab.ie.cuhk.edu.hk/projects/SRCNN.html} (deep convolutional networks), and Dong \textit{et al.} \cite{fsrcnn}\footnote{http://mmlab.ie.cuhk.edu.hk/projects/FSRCNN.html} (deep convolutional networks) along with one of the most popular technique, bicubic interpolation. The results of the existing super-resolution algorithms are computed by using the models provided by the authors at the links provided in the footnotes. It is to be noted that not all the algorithms support all the levels of magnification. For instance, the algorithm proposed by Kim \textit{et al.} \cite{kwan} supports up to $4$ levels of magnification whereas, Yang \textit{et al.}'s algorithm supports up to 2 levels of magnification.

\textbf{Face Databases:} Table \ref{tab:dbase} summarizes the statistics of the databases in terms of training and testing partitions, along with the resolutions. Details of the databases are provided below: \\
\textbf{1. CMU Multi-PIE Dataset \cite{mpie}:} Images pertaining to $337$ subjects are selected with frontal pose, uniform illumination, and neutral expression. $100$ subjects are used for training while the remaining $237$ are in the test set. \\%Two images are selected per subject. One is kept in the high resolution gallery, while the other is used as probe. The probe images are synthetically downsampled to $8\times8$, $16\times16$, $24\times24$, $32\times32$, and $48\times48$.
\textbf{2. CAS-PEAL Dataset \cite{caspeal}} consists of face images of $1040$ subjects. All subjects have a single, high-resolution \textit{normal} image and the dataset contains images of different covariates such as lighting, expression, and distance. For this research, \textit{normal} images are used as the high resolution gallery database while face images under the \textit{distance} covariate are downsampled and used as probe images. \\
\textbf{3. SCface Dataset \cite{scface}: }It consists of $130$ subjects, each having one high resolution frontal face image and multiple low resolution images, captured from three distances using surveillance cameras. \\
\textbf{4. Real World Scenarios Dataset \cite{himanshu}} contains images of seven subjects associated with the London Bombing, Boston Bombing, and Mumbai Attacks. Each subject has one high resolution gallery image and multiple low resolution test images. The test images are captured from surveillance cameras and are collected from multiple sources from the Internet. Since the number of subjects are just seven, in order to mimic a real world scenario, the gallery size is increased to create an \textit{extended} gallery of $1200$ subjects. Images from the Multi-PIE, ND Human Identification Set-B \cite{notredame}, and MEDS\cite{meds} datasets are used for the same. \\ \\
\textbf{Protocol:} For all the datasets, a real world matching protocol is followed. For each subject, multiple low resolution images are used as probe images which are matched against the pre-acquired database of high resolution gallery images. Only a single high resolution image per subject is used as gallery. The proposed and comparative algorithms are used to synthesize (or super-resolve) a high resolution image from a given low resolution input. The magnification factor varies from 2 (for probes of $48\times48$) to 12 (for probes of $8\times8$) to match it against the gallery database of size $96\times96$. For all the databases except the SCface, test images are of sizes varying from $8\times8$ to $48\times48$. For the SCface database, predefined protocol is followed and probe resolutions are $24\times24$, $32\times32$, and $48\times48$. Face detection is performed using face co-ordinates (if provided) or using Viola Jones Face Detector \cite{viola} and synthetic downsampling is performed to obtain lower resolutions.
All the experiments are performed with five times random sub-sampling to ensure consistency. \\
\textbf{Implementation Details:} The SDSR algorithm is trained using the pre-acquired gallery database for each dataset. The regularization constant for sparsity is kept at 0.85. Different dictionaries have different dimensions, based on the input data. For instance, the two-level dictionaries created for SCface dataset contain 100 and 80 atoms in the first and second dictionary respectively. The source code of the algorithm will be made publicly available in order to ensure reproducibility of the proposed approach.

\begin{table*}[]
\centering
\small
\caption{Rank-1 identification accuracies (\%) obtained using Luxand (COTS-II) for cross resolution face recognition. The target resolution is $96\times96$. The algorithms which do not support the required magnification factor are presented as $'-'$. }
\vspace{-10pt}
\label{luxandResults}
\begin{tabular}{|m{1.5em}|m{5em}|m{3.7em}|m{3.5em}|m{3.5em}|m{3.5em}|m{3.5em}|m{3.5em}|m{3.5em}|m{3.5em}|m{4em}|}
\hline
\multirow{2}{*}{} & \textbf{Probe Resolution} & \textbf{Original Image} & \textbf{Bicubic Interp.} & \textbf{Dong \textit{et al.} \cite{fsrcnn}} & \textbf{Kim \textit{et al.} \cite{kwan}} & \textbf{Gu \textit{et al.} \cite{gu_iccv15}} & \textbf{Dong \textit{et al.} \cite{srcnn}} &  \textbf{Peleg \textit{et al.} \cite{peleg}} & \textbf{Yang \textit{et al.} \cite{yang}} & \textbf{Proposed SDSR} \\
\hhline {|=|=|=|=|=|=|=|=|=|=|=|}

\multirow{5}{*}{\rotatebox[origin=c]{90}{\parbox[c]{2cm}{\centering \textbf{CMU Multi-PIE}}} }  &
8$\times$8 & 0.0$\pm$0.0 & 0.0$\pm$0.0 & - & - & - & - & - & - & \textbf{82.3$\pm$1.4} \\ \cline{2-11}
& 16$\times$16 & 0.0$\pm$0.0 & 0.0$\pm$0.0 & - & - & - & - & - & - & \textbf{90.5$\pm$1.1} \\ \cline{2-11}
& 24$\times$24 & 0.9$\pm$0.3 & 1.0$\pm$0.3& 2.3$\pm$0.5& 5.9$\pm$0.7& 6.8$\pm$1.4& 6.8$\pm$0.5 & - & - & \textbf{92.1$\pm$1.5} \\ \cline{2-11}
& 32$\times$32 & 11.3$\pm$1.1 & 18.3$\pm$7.1 & 13.5$\pm$0.6 & 28.6$\pm$1.2 & 24.3$\pm$2.3 & 19.4$\pm$1.5 & 17.4$\pm$2.5 & - & \textbf{92.2$\pm$1.6} \\ \cline{2-11}
& 48$\times$48 & 90.2$\pm$0.5 & \textbf{97.9$\pm$0.5} & 96.0$\pm$0.6 & 97.1$\pm$0.7 & 96.6$\pm$0.5 & 96.9$\pm$0.6 & 97.5$\pm$0.5 & 96.2$\pm$0.4 & 91.9$\pm$1.6 \\
\hhline {|=|=|=|=|=|=|=|=|=|=|=|}

\multirow{5}{*}{\begin{turn}{90}\textbf{CAS-PEAL}\end{turn}} &
8$\times$8 & 0.0$\pm$0.0 & 0.0$\pm$0.0 & - & - & - & -  & -  & - & \textbf{91.7$\pm$0.9} \\ \cline{2-11}
& 16$\times$16 & 0.0$\pm$0.0 & 0.6$\pm$0.6 & - & - & - & - & - & - & \textbf{93.3$\pm$0.7} \\ \cline{2-11}
& 24$\times$24 & 0.5$\pm$0.4 & 49.3$\pm$1.3 & 2.3$\pm$0.8 & 10.2$\pm$1.1 & 7.3$\pm$1.5 & 5.8$\pm$0.4 & - & - & \textbf{93.7$\pm$1.4} \\ \cline{2-11}
& 32$\times$32 & 11.1$\pm$2.8 & 92.5$\pm$2.0 & 27.9$\pm$1.1 & 34.6$\pm$2.3 & 31.7$\pm$2.3 & 15.2$\pm$3.3 & 28.0$\pm$1.9 & - & \textbf{93.9$\pm$1.3} \\ \cline{2-11}
& 48$\times$48 & 88.1$\pm$0.6 & \textbf{95.4$\pm$1.4} & 85.7$\pm$2.8 & 93.3$\pm$1.4 & 93.3$\pm$1.4 & 91.4$\pm$1.4 & 93.6$\pm$1.9 & 90.8$\pm$1.7 & 93.9$\pm$1.5\\ \cline{2-11}
\hhline {|=|=|=|=|=|=|=|=|=|=|=|}

\multirow{3}{*}{\begin{turn}{90}\textbf{SCface}\end{turn}} &
24$\times$24 & 1.1$\pm$0.2& 1.5$\pm$1.0& 1.2$\pm$0.5 & 0.8$\pm$0.1& 2.2$\pm$0.5 & 1.9$\pm$0.6 & - & - & \textbf{14.7$\pm$2.4} \\ \cline{2-11}
& 32$\times$32 & 2.2$\pm$0.4 & 3.2$\pm$0.4 & 3.5$\pm$0.5 & 2.6$\pm$0.7 & 4.0$\pm$0.7 & 2.6$\pm$1.0 & 2.8$\pm$0.7 & - & \textbf{15.7$\pm$1.3} \\ \cline{2-11}
& 48$\times$48 & 9.7$\pm$1.7& 12.6$\pm$1.7 & 9.6$\pm$1.1 & 11.6$\pm$1.3 & 10.1$\pm$1.8 & 11.7$\pm$2.0 & 11.4$\pm$1.2 & 11.9$\pm$1.0 & \textbf{19.1$\pm$3.4} \\ \hline
\end{tabular}
\vspace{-8pt}
\end{table*}

\section{Results and Analysis}
\label{sec:results}
The proposed algorithm is evaluated with three sets of experiments: (i) face recognition performance with resolution variations, (ii) image quality measure, and (iii) face identification analysis with different dictionary levels. The resolution of the gallery is set to $96\times96$. For the first experiment, the probe resolution varies from $8\times8$ to $48\times48$, while it is fixed to $24\times24$ for the next two experiments.

\subsection{Face Recognition across Resolutions}
For all datasets and resolutions, results are tabulated in Tables \ref{verilookResults} to \ref{realWorld}. The key observations pertaining to these set of experiments are presented below:

\noindent \textbf{$\mathbf{8\times8}$ and $\mathbf{16\times16}$ probe resolutions:} Except bicubic interpolation, none of the existing super resolution or synthesis algorithms used in this comparison support a magnification factor of $12$ (for $8\times8$) or $6$ (for $16\times16$); therefore, the results on these two resolutions are compared with original resolution (when the probe is used as input to COTS as it is, without any resolution enhancement) and bicubic interpolation only. As shown in the third and fourth columns of the two tables, on the CMU Multi-PIE and CAS-PEAL databases, matching with original and bicubic interpolated images results in an accuracy of $\leq 1.1\%$ whereas, the images synthesized using the proposed algorithm provide rank-1 accuracy of $82.6\%$ and $92.8\%$, respectively.

\begin{figure}[!t]
\centering
\includegraphics[width= 3in]{badSamples.pdf}
 \vspace{-5pt}
\caption{Sample images from SCface dataset incorrectly synthesized by the SDSR algorithm for $32\times32$ input. }
 \vspace{-15pt}
\label{bad}
\end{figure}

\noindent \textbf{$\mathbf{24\times24}$ and $\mathbf{32\times32}$ probe resolutions:} As shown in Table \ref{verilookResults}, on CMU Multi-PIE and CAS-PEAL databases with test resolution of $24\times24$ and $32\times32$, the synthesized images obtained using the proposed SDSR algorithm, yield a rank-1 accuracy of $\geq 91.8\%$. Other approaches yield a rank-1 accuracy of less than $20\%$, except bicubic interpolation on  $32\times32$ size which provides rank-1 accuracy of $76.5\%$. As shown in Table \ref{luxandResults}, similar performance trends are observed using COTS-II on the two databases. For SCface, the rank-1 accuracy with SDSR is significantly higher than the existing approaches; however, due to the challenging nature of the database, both commercial matchers provide low rank-1 accuracies. Fig. \ref{bad} presents sample images from the SCface dataset, incorrectly synthesized via the proposed SDSR algorithm. Varying acquisition devices of the training and testing partitions, along with the covariates of pose and illumination creates the problem further challenging.

\noindent \textbf{$\mathbf{48\times48}$ probe resolution:} Using COTS-I, the proposed algorithm achieves improved performance than other techniques, except on the CMU Multi-PIE dataset, where it does not perform as well. On all other databases, the proposed algorithm yields the best results. Upon analyzing both the Tables, it is clear that the proposed algorithm is robust to different recognition systems and performs well without any bias for a specific kind of recognition algorithm.

Another observation is that with COTS-II, images super-resolved using bicubic interpolation yield best results on the first two databases. However, it should be noted that these results are only observed for a magnification factor of $2$ and for images which were synthetically down-sampled. In real world surveillance datasets, such as SCface, the proposed approach performs best with both commercial systems.

\begin{table*}[]
\centering
\small
\caption{Real World Scenarios: Recognition accuracy obtained in top 20\% ranks, against a gallery of 1200 subjects using COTS-I (Verilook) having resolution of 96x96. }
\vspace{-10pt}
\label{realWorld}
\begin{tabular}{|m{4.6em}|m{3.9em}|m{4.8em}|m{4em}|m{4em}|m{4em}|m{4em}|m{4em}|m{4em}|m{4em}|}
\hline
\textbf{Probe Resolution} & \textbf{Original Image} & \textbf{Bicubic Interpolation} & \textbf{Dong \textit{et al.} \cite{fsrcnn}} & \textbf{Kim \textit{et al.} \cite{kwan}} & \textbf{Gu \textit{et al.} \cite{gu_iccv15}} & \textbf{Dong \textit{et al.} \cite{srcnn}} & \textbf{Peleg \textit{et al.} \cite{peleg}} & \textbf{Yang \textit{et al.} \cite{yang}} & {\textbf{Proposed SDSR}} \\
\hhline {|=|=|=|=|=|=|=|=|=|=|}

8$\times$8 & 0.0 & 0.0 & - & - & - & - & - & - & \textbf{53.3} \\
\hline
 16$\times$16 & 0.0 & 13.3 & - & - & - & - & - & - & \textbf{53.3} \\
 \hline
 24$\times$24 & 6.6 & 16.6 & 13.3 & 26.6 & 13.3 & 6.6 & - & - & \textbf{53.3} \\
 \hline
 32$\times$32 & 33.3 & 16.6 & 33.3 & 33.3 & 33.3 & 16.6 & 40.0 & - & \textbf{53.3} \\
 \hline
 48$\times$48 & 33.3 & 46.6 & 26.6 & 33.3 & 26.6 & 20.0 & 33.3 & 40.0 & \textbf{60.0} \\
\hline
\end{tabular}
\vspace{-8pt}
\end{table*}

\begin{table*}
\centering
\small
\caption{Average no reference quality measure - BRISQUE \cite{brisque} for probe resolution of $24\times24$ synthesized to $96\times96$, obtained over five folds. A lower value for BRISQUE corresponds to lesser distortions in the image.}
\vspace{-10pt}
\label{tab:quality}
\begin{tabular}{|k{7em}|k{7em}|k{6em}|k{6.1em}|k{6em}|k{6em}|k{7em}|}
\hline
\textbf{Database} & \textbf{Bicubic Interp.} & \textbf{Dong \textit{et al.} \cite{fsrcnn}} & \textbf{Kim \textit{et al.} \cite{kwan}} & \textbf{Gu \textit{et al.} \cite{gu_iccv15}} & \textbf{Dong \textit{et al.} \cite{srcnn}} & {\textbf{Proposed SDSR}} \\
\hhline {|=|=|=|=|=|=|=|}
CMU Multi-PIE & {54.8 $\pm$ 0.1} & 28.94 $\pm$ 0.0 & {50.8 $\pm$ 0.1} & {52.8 $\pm$ 0.1} & 48.8 $\pm$ 0.1 &  {\textbf{26.2 $\pm$ 1.3}} \\
\hline
CAS-PEAL & 60.0 $\pm$ 0.2 & 52.86 $\pm$ 0.0 & 54.3 $\pm$ 0.2 & 56.4 $\pm$ 0.1 & 53.4 $\pm$ 0.1 & \textbf{39.3 $\pm$ 0.3} \\
\hline
SCface & 58.7 $\pm$ 0.1 & 52.86 $\pm$ 0.0 & 53.2 $\pm$ 0.2 & 54.9 $\pm$ 0.1 & 47.2 $\pm$ 0.1 & \textbf{34.2 $\pm$ 0.6} \\
\hline
Real World & {57.5} &28.94 & {54.5} & {54.6} & 49.54 & {\textbf{25.9}} \\
\hline
\end{tabular}
\vspace{-10pt}
\end{table*}

\begin{figure}
\centering
\includegraphics[width= 3.2in]{24Samples}
\vspace{-5pt}
\caption{Probe images of $24\times24$ are super-resolved/synthesized to $96\times96$. (a) corresponds to the original probe, (b)-(f) correspond to different techniques: bicubic interpolation, Kim \textit{et al} \cite{kwan}, Gu \textit{et al.} \cite{gu_iccv15}, Dong \textit{et al.} \cite{srcnn}, Dong \textit{et al.} \cite{fsrcnn}, and the proposed SDSR algorithm.}
\vspace{-15pt}
\label{fig24x24}
\end{figure}

\noindent \textbf{Real World Scenarios Dataset:} Table \ref{realWorld} summarizes the results of COTS-I on Real World Scenarios dataset. Since the gallery contains images from $1200$ subjects, we summarize the results in terms of the identification performance with top 20\% retrieved matches. It is interesting to observe that for all test resolutions, the proposed algorithm significantly outperforms existing approaches. SDSR achieves a 53.3\% identification accuracy on probe resolution of $8\times8$ and an accuracy of 60.0\% for $48\times48$ test resolution.

\noindent \textbf{Cross Dataset Experiments:} The SDSR algorithm was trained on the CMU Multi-PIE dataset, and tested on the SCface dataset for a probe resolution of $24\times24$.
A rank-1 identification accuracy of 1.62\% (1.92\%) was obtained using COTS-I (COTS-II), whereas a rank-5 identification accuracy of 7.54\% and 9.06\% was obtained respectively. The results showcase that the proposed model is still able to achieve better recognition performance as compared to other techniques. However, the drop in accuracy strengthens our hypothesis that using an identity-aware model for performing synthesis is more beneficial for achieving higher classification performance.

\begin{table}
\centering
\small
\caption{Rank-1 accuracies (\%) for varying levels of SDSR algorithm with $24\times24$ probe and $96\times96$ gallery. }
\vspace{-10pt}
\label{proposedLevels}
\begin{tabular}{|m{5em}|m{3.8em}|m{3.8em}|m{3.8em}|m{3.8em}|}
\hline
\multirow{2}{*}{\textbf{Database}} & \multirow{2}{*}{\textbf{COTS}} & \multicolumn{3}{c|}{\textbf{Dictionary Levels}} \\\cline{3-5}
& & \textbf{$k=1$} & \textbf{$k=2$} & \textbf{$k=3$} \\\hline

\textbf{CMU} &Verilook & 91.4 & \textbf{91.8} & \textbf{91.8}\\ \cline {2-5}
\textbf{Multi-PIE} & Luxand & 92.0 & 92.1 & \textbf{92.5}\\ \hline

\multirow{2}{*}{\textbf{CAS-PEAL}} & Verilook & 93.8 & \textbf{95.3} & 93.7 \\\cline {2-5}
& Luxand & 92.2 & \textbf{93.7}  & 93.6 \\\hline

\multirow{2}{*}{\textbf{SCface}} & Verilook & 15.0 & 14.7  & \textbf{15.2} \\ \cline {2-5}
& Luxand & \textbf{15.6} & 14.7 & 15.3 \\ \hline
\end{tabular}
\label{tabLevels}
\vspace{-15pt}
\end{table}

\subsection{Quality Analysis}
Fig. \ref{fig24x24} shows examples of synthesized/super-resolved images from multiple databases generated using the proposed and existing algorithms. In this figure, images of $96\times96$ are synthesized from low resolution images of $24\times24$. It can be observed that the output images obtained using existing algorithms (columns (b) - (f)) have artifacts in terms of blockiness and/or blurriness. However, the quality of the images obtained using the proposed algorithm (column (g)) are significantly better than the other algorithms. To compare the visual quality of the outputs, a no reference image quality measure, BRISQUE \cite{brisque} is utilized. Blind/Referenceless Image Spatial QUality Evaluator (BRISQUE) computes the distortion in the image by using the statistics of locally normalized luminance coefficients. It is calculated in the spatial domain and is used to estimate the losses of naturalness in an image. Lower the value, less distorted is an image. From Table \ref{tab:quality}, it can be seen that  images obtained using the proposed SDSR algorithm have a better (lower) BRISQUE score as compared to images generated with existing algorithms; a difference of at least $15$ points is observed in the BRISQUE scores.

\subsection{Effect of Dictionary Levels}
As explained in the algorithm section, synthesis can be performed at different levels of deep dictionary, i.e. with varying values of $k$. This experiment is performed to analyze the effect of different dictionary levels on identification performance. The proposed algorithm is used to synthesize high resolution images ($96\times96$, magnification factor of 4) from input images of size $24\times24$ with varying dictionary levels, i.e. $k=1, 2, 3$.  First level dictionary ($k=1$) is equivalent to shallow dictionary learning, whereas two and three levels correspond to synthesis with deep dictionary learning. Table \ref{tabLevels} reports the rank-1 identification accuracies obtained with the two commercial matchers for four databases. The results show that the proposed approach with $k=2$, generally, yields the best results. In some cases, the proposed approach with $k=3$ yields better results. Generally, abstraction capability of deeper layers and overfitting are two effects in deep learning based approaches. In Table \ref{proposedLevels}, we observe the trade-off between these two. Most of the datasets are moderately sized; therefore, we observe good results in the second layer. In the third layer, \textit{overfitting} offsets the \textit{abstraction}, hence we see none to marginal changes. Further, computational complexity with 3-level deep dictionary features is higher and the improvements in accuracy are not consistent across databases. On the other hand, paired t-test on the results obtained by the shallow dictionary and 2-level deep dictionary demonstrate statistical significance even with a confidence level of 95\% (for Verilook). Specifically, for a single image, synthesis with level-1 dictionary requires 0.42 ms, level-2 requires 0.43 ms, and level-3 requires 0.45 ms.

\section{Conclusion}
The key contribution of this research is a recognition-oriented pre-processing module based on dictionary learning algorithm for synthesizing a high resolution face image from low resolution input. The proposed SDSR algorithm learns the representations of low and high resolution images in a hierarchical manner along with a transformation between the representations of the two. The results are demonstrated on four databases with test image resolutions ranging from $8\times8$ to $48\times48$. Matching these requires generating synthesized high resolution images with a magnification factor of $2$ to $12$. Results computed in terms of both image quality measure and face recognition performance illustrate that the proposed algorithm consistently yields good recognition results. Computationally, the proposed algorithm requires less than 1 millisecond for generating a synthesized high resolution image which further showcases the efficacy and usability of the algorithm for low resolution face recognition applications.

{\small
\bibliographystyle{ieee}


\section{Introduction}

Physical laws are strikingly simple, although there is no \textit{a priori} reason they must be so. The principle of simplicity plays a crucial role in the discovery and the evaluation of physical laws. However, there are unresolved philosophical issues: what the principle of simplicity is; how it is measured; how it is justified; and how it is related to truth and the world.

Debates in philosophy of science have focused on the connection (or the lack thereof) between simplicity and truth.   In this paper, I suggest that a fruitful way forward is to focus instead on the connection between simplicity and lawhood, in the framework of nomic realism (to be defined below). I propose a new principle of simplicity that fills an epistemic gap in both Humean and non-Humean accounts of lawhood.  This approach solves some difficult problems about laws and simplicity. As a bonus, we come to see that Humeanism has no genuine epistemic advantage over non-Humeanism.

Let \textit{nomic realism} denote the conjunction of the following two theses:

\begin{description}
  \item[Metaphysical Realism:] Physical laws are objective and mind-independent; more precisely, which propositions express physical laws are objective and mind-independent facts in the world.\footnote{A weaker version of metaphysical realism maintains that laws are not entirely mind-dependent. That would accommodate more pragmatic versions of the Humean best-system accounts.}
\end{description}

\begin{description}
  \item[Epistemic Realism:] We have epistemic access to physical laws; more precisely, we can be epistemically justified in believing which propositions express the physical laws, given the evidence that we will in fact obtain.\footnote{The terminology is due to \cite{earman2005contact}. Here I've added the clause ``given the evidence that we will in fact obtain.''  My version of epistemic realism is logically stronger than theirs. }
\end{description}
There is tension between these two aspects of nomic realism. If laws are out there in the world and not (entirely) mind-dependent, how can we claim epistemic access to the laws given our finite and limited evidence? Contrary to appearances, the tension exists in both Humean and non-Humean accounts of laws, since on both accounts laws are not a consequence of our actual evidence.

The problem can be sharpened by considering cases of empirical equivalence. If two physical laws are empirically equivalent, yielding  the same data and making  the same predictions, what justifies the acceptance of one law over the other? Some philosophers have tried to resist anti-realist arguments from empirical equivalence by disputing whether there really are genuine cases of empirical equivalence. They are correct  that some algorithms for generating empirical equivalents are bordering on Cartesian skepticism \citep{stanford2006exceeding}.\footnote{They generate, for example, the hypothesis that the universe is a computer simulation. } However, there are ``non-skeptical'' algorithms that generate empirical equivalents (of varying degrees of complexity). I propose three new classes of algorithms that are inspired by recent discussions in philosophy of physics. They demonstrate that there is a  significant gap between metaphysical realism and epistemic realism.

A promising solution is to invoke simplicity as a criterion to choose among empirically equivalent rivals:

\begin{description}
  \item[Guide-to-Truth:] Simpler candidates are more likely to be true.
\end{description}
 However, this principle is problematic. In addition to the problem of precision and the problem of justification, Guide-to-Truth just seems false. First, we live in a fairly complicated world where truths are not simple. Second, the idea that simpler laws are more likely to be true is probabilistically incoherent,  because it conflicts with the axioms of probability in cases of nested theories.

I suggest that nomic realists should embrace a new principle of simplicity:
\begin{description}
  \item[Guide-to-Lawhood:] Simpler candidates are more likely to be laws.
\end{description}
Guide-to-Lawhood solves the problem of nested theories in a straightforward way and secures epistemic realism in the face of new cases of empirical equivalence. However, the principle is, in several aspects, more modest than the usual posits of simplicity in the literature. For example, the new principle can be vague, comparative,  merely partial in the ordering of candidates for laws, and compatible with the complexity in the mosaic. Moreover, it need not be the only such guide; other theoretical virtues can also earn their places by contributing to epistemic realism.

Properly understood, Guide-to-Lawhood does not follow from the Humean best-system account of lawhood (BSA), but it must be added to BSA as an independent epistemic norm that constrains our beliefs about the best system when our evidence about the mosaic is fairly limited. Since both Humeanism and non-Humeanism need this independent posit, they are on a par regarding the empirical discovery of laws. As a consequence, the often-cited epistemic advantage of the former over the latter is exaggerated. This undercuts an influential epistemic argument for Humeanism \citep{earman2005contact}.

The framework above suggests a new strategy to argue for simplicity as a fundamental epistemic guide. Given the intimate connection between laws and induction, we have reasons to believe that the rationality of induction presupposes the simplicity of physical laws. The inference can be supported by considering the class of time-dependent laws.  The development of this argument is left to a longer version of the paper.

\section{Puzzles about Laws and Simplicity}

In this section, I discuss some puzzles about nomic realism and standard posits of simplicity. They motivate the search for a better principle of simplicity and a more nuanced understanding of nomic realism.

\subsection{A Puzzle about Nomic Realism}

We have seen that there is tension between  two aspects of nomic realism---metaphysical realism and epistemic realism.  For concreteness, let us look at a Humean account and a non-Humean account that aspire to satisfy nomic realism. The way the tension shows up in these two accounts is representative of a large class of realist accounts of lawhood.

First, consider the Humean best-system account of \cite{LewisCounterfactuals}, with some slight modifications:
\begin{description}
  \item[Best System Account (BSA)]   Fundamental laws of nature are the axioms of the best system that summarizes the mosaic and optimally balances simplicity, informativeness, fit, and degree of naturalness of the properties referred to. The mosaic (spacetime and its material contents) contains only local matters of particular fact, and the mosaic is the complete collection of fundamental facts. The best system supervenes on the mosaic.\footnote{A key difference between this version and Lewis's \citep{LewisCounterfactuals, LewisNWTU, lewis1986philosophical} is that the latter but not the former requires fundamental laws to be regularities. The other difference is the replacement of perfect naturalness with degree of naturalness. See \cite[sect.2.3]{chen2018NV} for more in-depth comparisons. On Humeanism, the mosaic is often required to be about local matters of particular fact. }
  \end{description}
  BSA satisfies metaphysical realism, even though laws are not metaphysically fundamental on this approach. Given a particular mosaic (spacetime manifold with material contents), there is a unique best system that is objectively best.\footnote{For the sake of argument, I set aside the worry of ``ratbag idealism'' and  grant Lewis's assumption that nature is kind to us \cite[p.479]{LewisHSD}. Even if BSA satisfies the weaker version of metaphysical realism where laws are not entirely mind-dependent, it does not automatically secure epistemic realism. Hence, this discussion also applies to recent versions of pragmatic Humeanism.}

For another example, consider a recent non-Humean account according to which laws govern and exist over and above the material contents  \citep{chenandgoldstein}:
  \begin{description}
  \item[Minimal Primitivism (MinP)] Fundamental laws of nature are certain primitive facts about the world. There is no restriction on the form of the fundamental laws.  They govern the behavior of material objects by constraining the physical possibilities.
\end{description}
MinP satisfies metaphysical realism, because the primitive facts about the world are taken to be objective and mind-independent.

Now, do BSA and MinP vindicate epistemic realism? Their metaphysical posits, by themselves, do not guarantee epistemic realism. This should be clear on MinP. Since there is no metaphysical restriction on the form of the fundamental laws, and if they are entirely mind-independent primitive facts about the world, how do we know which propositions are the laws? This is an instance of the tension between metaphysical and epistemic realism. However, I suggest that an analogous problem exists on BSA.  How could that be? It is often thought that BSA has an epistemic advantage over non-Humean accounts like MinP, precisely because BSA brings laws closer to us so that we can have epistemic access to them. BSA defines laws in terms of the mosaic, and the mosaic is all we can empirically access.

The problem is that we are not given the mosaic. Just as MinP requires an extra epistemic principle to infer what the laws are, BSA requires a similar principle to infer what the mosaic is like. The latter turns out to be mediated by an extra epistemic principle of what we should expect about the best system, given our limited evidence.

To sharpen the discussion, let us suppose, granting Lewis's assumption of the kindness of nature \cite[p.479]{LewisHSD},  that given the mosaic $\xi$ there is a unique best system whose axioms express the fundamental law $L$:
\begin{equation}
	L = BS(\xi)
\end{equation}
with $BS(\cdot)$ the function that maps a mosaic to its best-system law. Let us stipulate that for both BSA and MinP,  physical reality is described by a pair $(L, \xi)$. For both, we must have that $\xi \in \Omega^L$, with $\Omega^L$ the set of mosaics compatible with $L$. This means that $L$ is true in $\xi$.  On BSA, we also have that 	$L = BS(\xi)$. So in a sense, all we need in BSA is $\xi$; $L$ is not ontologically extra. But it does not follow that BSA and MinP are relevantly different when it comes to epistemic realism.

Let $E$ denote our evidence consisting in observational data about  physical reality. Let us be generous and allow $E$ to include not just our current evidence but also all past evidence and all future evidence about the universe that we will in fact gather.  There are two salient features of $E$:

\begin{itemize}
  \item $E$ does not pin down a unique $\xi$. There are different candidates of $\xi$ that yield the same $E$. (After all, $E$ is a spatiotemporally partial and macroscopically coarse-grained description of $\xi$.)
  \item  $E$ does not pin down a unique $L$.  There are different candidates of $L$ that yield the same $E$. (On BSA, this is an instance of the previous point; on MinP, this is even clearer since $L$ can vary independently of $\xi$, up to a point.)
\end{itemize}
Hence, on BSA, just as on MinP, $E$ does not pin down $(L, \xi)$. There is a gap between what our evidence entails and what the laws are.

The gap becomes clearer when we consider cases of empirical equivalence.\footnote{Here, I use a fairly weak notion of empirical equivalence, where $L_1$ and $L_2$ are empirically equivalent with respect to actual evidence $E$ just in case $E$ is compatible with $L_1$ and $L_2$. This criterion, with the emphasis on actual data $E$, is weaker than the notion of empirical equivalence according to which two laws should agree not just on the actual data but all (nomologically) possible data. I will drop the explicit reference to $E$ in what follows. Now, for those who want to consider the stronger criterion of empirical equivalence, the arguments below can be modified. If we consider all possible data, we should also consider probability distributions over models in the theory, and compare the likelihoods of $E$. This does not change the dialectics, as there exist probability distributions that yield equal likelihood of $E$.   } If different laws yield the same evidence, it is puzzling how we can be epistemically justified in choosing one over its empirically equivalent rivals, unless we rule them out by positing substantive assumptions that go beyond the metaphysical posits of nomic realism. In the literature (see for example \cite{kukla1998studies}), there are suggestions about how to algorithmically generate empirically equivalent rivals, but some of them border on Cartesian skepticism. Here I offer three new kinds of algorithms, based on recent discussions in philosophy of physics. They have much more limited scopes, but they suffice to show that the gap exists on nomic realism. \\

\noindent
\textbf{Algorithm A: Moving parts of ontology (what there is in the mosaic) into the nomology (the package of laws)}.

   \textit{General strategy.} This strategy works on both BSA and MinP. Given a theory of physical reality $T_1=(L, \xi)$, if $\xi$ can be decomposed into two parts $\xi_1 \& \xi_2$,  we can construct an empirically equivalent rival $T_2 = (L\&\xi_1, \xi_2)$, where $\xi_1$ is moved from  ontology to nomology.

\textit{Example.}  Consider the standard theory of Maxwellian electrodynamics, $T_{M1}$:
  \begin{itemize}
  \item   Nomology: Maxwell's equations and Lorentz force law
  \item Ontology: a Minkowski spacetime occupied by charged particles with trajectories $Q(t)$ and an electromagnetic field $F(x,t)$.
\end{itemize}

Here is an empirically equivalent rival, $T_{M2}$:
  \begin{itemize}
  \item   Nomology: Maxwell's equations, Lorentz force law, and an enormously complicated law specifying the exact functional form of $F(x,t)$ that appears in the dynamical equations
  \item Ontology: a Minkowski spacetime occupied by charged particles with trajectories $Q(t)$
\end{itemize}
Our evidence $E$ is compatible with both $T_{M1}$ and $T_{M2}$. The outcome of every experiment in the actual world will be consistent with $T_{M2}$, as long as the outcome is registered as certain macroscopic configuration of particles \citep{bell2004speakable}. We can think of the new law in $T_{M2}$ as akin to the Hamiltonian function in classical mechanics, which is interpreted as encoding all the classical force laws, except that specifying $F(x,t)$ is much more complicated than specifying a typical Hamiltonian. Both $F(x,t)$ and the Hamiltonian are components of respective laws of nature that tell particles how to move.\footnote{Note that we can  decompose the standard ontology in many other dimensions, corresponding to more ways to generate empirically equivalent laws for a Maxwellian world. This move is discussed at length by \cite{AlbertLPT}. Similar strategies have been considered in the ``quantum Humeanism'' literature. See \cite{miller2013quantum}, \cite{esfeld2014quantum}, \cite{callender2015one, bhogal2015humean}, and \cite{chen2018HU}.  }\\

\noindent
\textbf{Algorithm B: Changing the nomology directly}.

 \textit{  General strategy.}  This strategy is designed for MinP.  We can generate empirical equivalence by directly changing the nomology. Suppose the actual mosaic $\xi$ is governed by the  law $L_1$. Consider $L_2$, where $\Omega^{L_1} \neq \Omega^{L_2}$ and $\xi \in \Omega^{L_2}$.  $L_1$ and $L_2$ are distinct laws because they have distinct sets of models. Since $E$ (which can be regarded as a coarse-grained and partial description of $\xi$) can arise from both, the two laws are empirically equivalent.  There are infinitely many such candidates for $\Omega^{L_2}$. For example, $\Omega^{L_2}$ can be obtained by replacing one mosaic in $\Omega^{L_1}$ with something different and not already a member of $\Omega^{L_1}$, by adding some mosaics to $\Omega^{L_1}$, or by removing some mosaics in $\Omega^{L_1}$.  $L_2$ is empirically equivalent with $L_1$ since $E$ is compatible with both.\footnote{See \cite{manchak2009can, manchak2020global} for more examples.}

 \textit{Example.} Let $L_1$ be the Einstein equation of general relativity, with  $\Omega^{L_1}=\Omega^{GR}$, the set of general relativistic spacetimes. Assume that the actual spacetime is governed by $L_1$, so that $\xi\in \Omega^{L_1}$. Consider $L_2$, a law that permits only the actual spacetime and completely specifies its microscopic detail, with $\Omega^{L_2}=\{\xi\}.$ Since our evidence $E$ arises from $\xi$, it is compatible with both $L_1$ and $L_2$. Since it needs to encode the exact detail of $\xi$, $L_2$ is much more complicated than $L_1$.\footnote{$L_2$ is a case of strong determinism. See \cite{adlam2021determinism} and \cite{chen2022strong} for recent discussions.} \\

  \noindent
\textbf{Algorithm C: Changing the nomology by changing the ontology}.

 \textit{  General strategy.}  This strategy is designed for BSA. On BSA, we can change the nomology by making suitable changes in the ontology (mosaic), which will in general change what the best system is. Suppose the actual mosaic $\xi$ is optimally described by the actual best system $L_1=BS(\xi)$. We can a slightly different mosaic   $\xi'$, such that it differs from $\xi$ in some spatiotemporal region that is never observed and yet $E$ is compatible with both $\xi$ and $\xi'$. There are infinitely many such candidates for $\xi'$ whose best system $L_2=BS(\xi')$ differs from $L_1$. Alternatively, we can also expand $\xi$ to  $\xi' \neq \xi$ such that $\xi$ is a proper part of $\xi'$. There are many such candidates for $\xi'$ whose best system $L_2=BS(\xi')$ differs from $L_1$, even though $E$ is compatible with all of them.

\textit{Example.} Let $L_1$ be the Einstein equation of general relativity, with  $\Omega^{L_1}=\Omega^{GR}$, the set of general relativistic spacetimes. Assume that the actual spacetime is optimally described by $L_1$, so that $L_1 = BS(\xi)$. Consider $\xi'$, which differs from $\xi$ in only the number of particles in a small spacetime region $R$ in a far away galaxy that no direct observation is ever made. Since the number of particles is an invariant property of general relativity, it is left unchanged after a ``hole transformation'' \citep{sep-spacetime-holearg}.  We can use determinism to deduce that $\xi'$ is incompatible with general relativity, so that $L_1 \neq BS(\xi')$. Let $L_2$ denote $BS(\xi')$. $L_1\neq L_2$ and yet they are compatible with the same evidence we obtain in $\xi$.  Since $\xi'$ violates the conservation of number of particles and perhaps smoothness conditions, $L_2$ should be more complicated than $L_1$.

To be sure, we can also combine these algorithms to produce more sophisticated examples of empirical equivalence.\footnote{For example, in certain settings, we can change both the ontology and the nomology  to achieve empirical equivalence. For every wave-function realist theory, there is an empirically equivalent density-matrix realist theory. Their ontology and nomology are different, but no experiment can determine which is correct. }
 Here we have three algorithms with different strategies and scopes that can establish the existence of empirically equivalent rival laws, for a world like ours. They are inspired by recent discussions in philosophy of physics. None of them requires Cartesian skepticism. If such algorithms are allowed, how can we maintain epistemic realism? We may summarize the puzzle about nomic realism:
\begin{description}
  \item[Puzzle about Nomic Realism:] In such cases of empirical equivalence, what justifies the acceptance of one candidate law over the other?
\end{description}

\subsection{A Puzzle about Simplicity}

It has been recognized, correctly on my view,  that nomic realists need to invoke theoretical virtues as a way to choose among empirically equivalent laws underdetermined by evidence. An important example is the \textit{principle of simplicity} (PoS), according to which, roughly speaking, simpler laws are better, and perhaps more likely to be true. The basic idea is that simplicity is a guide to truth.   It has an intuitive appeal, as the paradigm examples of physical laws are strikingly simple and simpler than other candidates that yield the same data. Moreover, in the examples of empirical equivalence discussed before, the simpler law does seem like the better candidate.

However, PoS faces its own challenges. First, there is a problem of precision. It is difficult to say exactly what simplicity is and how simplicity should be measured. Should it be measured in terms of the number of equations, concepts, and parameters used in specifying the laws? Should they be traded off against each other?  Second, there is a problem of justification.  It is difficult to justify PoS in terms of epistemic principles.  If PoS cannot be justified further on epistemic grounds, what epistemic justification can it confer?

The problem of precision and the problem of justification do not show that PoS is wrong. They can be regarded as open research problems.  There is, however, a more urgent problem, because it seems to suggest that PoS is false or incoherent. That is the problem of nested theories, or sometimes called the problem of logical constraints.\footnote{This was first raised by \cite{popper2005logic} against the Bayesian proposal of \cite{wrinch1921xlii}. For recent discussions, see \cite{sober2015ockham} and \cite{henderson2022inference}.}

 The most straightforward formulation of PoS is that it is a fundamental epistemic guide to \textit{truth}. In probabilistic terms, it means that, for two propositions $L_1$ and $L_2$, if $L_1$ is simpler than $L_2$ then $L_1$ is more likely to be true than $L_2$. But this leads to probabilistic incoherence.

Whenever two theories have nested sets of models, say $\Omega^{L_1} \subset \Omega^{L_2}$,  the probability that $L_1$ is true cannot be higher than the probability that $L_2$ is true. For example, let $\Omega^{GR}$ denote the set of models compatible with the fundamental law in general relativity---the Einstein equation, and let $\Omega^{GR^+}$ denote the union of  $\Omega^{GR}$ and a few random spacetime models that do not satisfy the Einstein equation. Suppose there is no simple law that generates $\Omega^{GR^+}$. While the law of $GR$ (the Einstein equation) is presumably simpler than that of $GR^+$, the former cannot be more likely to be true than the latter, since every model of  $GR$ is a model of $GR^+$, and not every model of $GR^+$ is a model of $GR$. This is an instance of the problem of nested theories, as $\Omega^{GR}$ is a subclass of and nested within $\Omega^{GR^+}$.

Hence, it is probabilistic incoherent to maintain that simpler laws are more likely to be true. We may summarize the puzzle:
\begin{description}
  \item[Puzzle about Simplicity:] If simplicity is not a guide to truth, what is it a guide to?
\end{description}
That question shall be a clue for a new principle of simplicity.

 \section{Simplicity as a Fundamental Epistemic Guide to Lawhood}

 I propose that \textit{simplicity is a fundamental epistemic guide to lawhood}. Roughly speaking, simpler candidates are more likely to be laws, all else being equal.  This principle solves the problem of nested theories in a straightforward way. It also secures epistemic realism in cases of empirical equivalence where simplicity is the deciding factor.

 The principle is to be contrasted from the simplicity criterion in the Humean best-system account of lawhood. They are different kinds of principles: the latter is a metaphysical definition of what laws are, while the former is an epistemic principle concerning ampliative inferences based on our total evidence. Even if a Humean expects that the best system is no more complex than the mosaic, it does not follow that she should expect that the best system is relatively simple, since there is no metaphysical guarantee that the mosaic is ``cooperative.'' Both Humeans and non-Humeans can be uncertain about the laws, and both need a new principle to justify epistemic realism. If Humeans are epistemically warranted in making such a posit,  non-Humeans are too.

 I clarify the key terms below.

 \subsection{ \textit{Simplicity}}

  What is the measure of simplicity invoked here? It is unrealistic to insist that there is a single measure of simplicity regarding physical laws. There are many aspects of simplicity, as shown by recent works in computational complexity, statistical testing, and philosophy of science. Among them are: number of adjustable parameters, lengths of axioms, algorithmic simplicity, and conceptual simplicity.\footnote{For an overview of these different measures, see \cite{sep-simplicity} and \cite{iep-simplicity}.} Certain laws may employ more unified concepts, better achieving one dimension of simplicity, but require longer statements and hence do less well in other dimensions of simplicity. There need not be any precise way of trading off one over the other. Moreover, not all laws must take the form of differential equations; there can be boundary-condition laws and conservation laws. It is unreasonable to expect a single principle can be applied   to all  different forms of laws. I suggest that we take simplicity to be measured in a holistic (albeit vague) way, taking into account these different aspects of simplicity.\footnote{Alternatively, we may take simplicity as a family of concepts, and the principle of simplicity as a family of principles.}

The vagueness of simplicity might seems like as a problem for nomic realists. However, what matters to a realist who believes in simplicity is that there is enough consensus around the paradigm cases. There are hard cases of simplicity comparisons, but there are also clearcut cases, such as  $T_{M1}$ and its empirical equivalents generated by Algorithm A, or  general relativity and its empirical equivalents generated by Algorithms B and C.  This is similar to Lewis's assumption that Nature is kind to us and the borderline cases do not show up in realistic comparisons. The vagueness of simplicity here is no worse  than the problem in the BSA account of lawhood.

 The vagueness of simplicity does not imply that there are no facts about simplicity comparisons. Let us think about an analogy with moral philosophy. Judgments about moral values are also holistic and vague. While there are moral disagreements about hard cases, there can still be facts about whether helping a neighbor in need is morally better than beating the neighbor out of the blue. Moral realists maintain that we have robust moral intuition in the paradigm cases,  which need not be threatened by the existence of borderline cases. Sometimes different moral considerations conflict. In such cases, we may need to trade-off one factor against another.

 Given the vagueness of the simplicity postulate, we should not expect there be a total order that ranks theories from the most to the least simple. Instead, there may be multiple chains of partial orders, where each is connected by a "simpler than" relation $>_S$.\footnote{Hence, there may be pairs of theories that cannot be compared with respect to simplicity. If $A$ and $B$ are such a pair, then none of ``$>_S$,'' ``$<_S$,'' and ``$=_S$'' applies to them. We should allow cases of incommensurability or incomparability regarding simplicity. This relation can be denoted by $A \circledast B$.}

  \subsection{ \textit{Guide}}

What does it mean for simplicity to be a guide? A guide is not a guarantee. Inferences in the context of uncertainty, even when epistemically justified, are fallible. We can make mistakes when relying on the principle of simplicity.  Perhaps  the actual physical laws appear less simple than the ones we regard as laws, based on the principle of simplicity. I think a realist should admit this possibility. Indeed it is a hallmark of realism that we can be wrong, even when we follow scientific methodology. This uncertainty can be formulated in terms of comparative probability (where higher probability does not guarantee certainty):

\begin{description}
  \item[Simplicity Comparison:] Other factors being equal, if $A>_S B$, then $L[A] >_P L[B]$, where $>_S$ represents the comparative simplicity relation, $>_P$ represents the comparative probability relation,   $L[\cdot]$ denotes \textit{is a law}, which is an operator that maps a proposition to one about lawhood.\footnote{For example, $L[F=ma]$ expresses the proposition that \textit{F=ma is a law}. The proposition \textit{F=ma} is what \cite{lange2009laws} calls a ``sub-nomic proposition.'' }
\end{description}
But often other factors are not held equal, and we need to consider overall comparisons of theoretical virtues (epistemic guides). Other theoretical virtues can also serve as epistemic guides for lawhood. For example, informativeness and naturalness are two such virtues. A simple equation that does not describe much or describe things in too gruesome manners is less likely to be a law. How to trade off simplicity  against  other virtues can be another source of vagueness.

We can formulate a more general principle:
\begin{description}
  \item[Overall Comparison:] If $A>_O B$, then $L[A] >_P L[B]$, where $>_O$ represents the relation of overall comparison, of which $>_S$ is a contributing factor.
\end{description}
Since $>_O$ need not induce a total order of all  possible candidate laws, the corresponding $>_P$ need not induce a total order either.\footnote{There are theories that are related by $ \circledast$. However, in the cases of empirical equivalence discussed in \S2, there are clear winners in terms of overall comparison. } What is overall better is a holistic matter, and it can involve trade-offs among the theoretical virtues such as simplicity, informativeness, and naturalness.

The formulation in terms of comparative probability is much more modest  than  earlier objective Bayesian accounts that insist on a single simplicity measure, a single probability distribution, and the condition of normalizability.\footnote{For example, \cite{wrinch1921xlii} insist on normalization of a single probability distribution, which involves somewhat arbitrary assignments of probabilities to candidate laws. For a discussion, see \cite{sober2015ockham}.} The problem of non-normalizability does not arise, since we do not require a single probability distribution on the space of possible laws.

  \subsection{ \textit{Lawhood}}
What is the difference between Guide-to-Truth and Guide-to-Lawhood? The latter but not the former solves the problem of nested theories.  Recall the earlier example of $GR$ and $GR^+$. Even though we think that the Einstein equation is more likely to be a law, it is less likely to be true than the law of $GR^+$. I suggest that what simplicity selects here is not truth in general, but truth about lawhood, i.e. whether a certain proposition has the property of being a fundamental law.

Let us assume that fundamental lawhood is factive, which is granted on both BSA and MinP. Hence, lawhood implies truth:  $L[p] \Rightarrow p$. However, truth does not imply lawhood:   $p \nRightarrow L[p]$.  This shows that $L[p]$ is logically inequivalent to $p$. This is the key to solve the problem of nested theories.

 On Guide-to-Truth, in the case of nested theories, we have probabilistic incoherence. If $L_1$ is simpler than $L_2$, applying the principle that simpler laws are more likely to be true, we have $L_1 >_P L_2$. However, if $L_1$ and $L_2$ are nested with $\Omega^{L_1} \subset \Omega^{L_2}$,  the axioms of probability entail that  $L_1 \leq_P L_2$. Contradiction!

On Guide-to-Lawhood, the contradiction is removed, because \textit{more likely to be a law} does not entail \textit{more likely to be true}.  If $L_1$ and $L_2$ are nested, where $L_1$ is simpler than $L_2$ but  $\Omega^{L_1} \subset \Omega^{L_2}$, then $L_1 \leq_P L_2$. It is compatible with the fact that  $L[L_1] >_P L[L_2]$. What we have is an inequality chain:
 \begin{equation}
 L[L_2] <_P L[L_1] \leq_P L_1 \leq_P L_2
\end{equation}
This is a new solution to the problem of nested theories. It is compatible with but less demanding and perhaps more general than the recent proposal of \cite{henderson2022inference}. Unlike Henderson's approach, my proposal works even when candidate laws are not structured in a hierarchy.

 \subsection{ \textit{Epistemic}}

Why should we regard the Guide-to-Lawhood principle as an epistemic principle? Like many substantive (not merely structural) epistemic principles, it does not follow from self-evident premises. However, we may consider an argument from reflective equilibrium.   There are many cases of empirical equivalence where the salient difference between the empirical equivalents is their relative complexity. For example, if we are epistemically justified in accepting $T_{M1}$ over $T_{M2}$ because the former has simpler laws,  or in accepting $GR$ over $GR^+$ because the former has simpler laws, simplicity has to be an epistemic guide.\footnote{For a similar argument, see \cite{lycan2002explanation}.}

 Reflecting on our judgments over those cases, we may conclude that simplicity as a guide to lawhood is one posit we should make to justify epistemic realism about laws. It is what we  presuppose when we set aside (or give less credence to) those empirical equivalents as epistemically irrelevant.  For our preferences in the cases of empirical equivalence to be epistemically justified, the principle of simplicity should be an epistemic guide. As such, it is not merely a pragmatic principle, although it may have pragmatic benefits.  Simpler laws may be easier to conceive, manipulate, falsify, and the like. But if it is an epistemic guide, it is ultimately aiming at  certain truths about lawhood and providing epistemic justifications for our believing in such truths. There is, to be sure, the option of retreating from epistemic realism. But it is not  open to nomic realists.

  \subsection{ \textit{Fundamental}}

Why should we regard Guide-to-Lawhood as a \textit{fundamental} epistemic principle? The reason is that in the cases of empirical equivalence discussed above, the principle cannot be reduced to other epistemic principles that are more closely connected to lawhood or truth. I suggest that it is a rock-bottom principle that need not be justified further; it is an assumption we ought to adopt prior to empirical investigation. The reductive approaches to  simplicity in the literature do not apply in the case of empirical equivalence. For example, the AIC model-selection criterion advocated by \cite{forster1994tell} is designed for predictively inequivalent theories. In the absence of any successful reduction of simplicity to resolve cases of empirical equivalence, it is warranted to regard it as a fundamental epistemic guide. Admittedly, if someone presents a proof that simplicity can be reduced to something else, we should be open to the idea and regard the principle of simplicity as derivative of some deeper principle. However, the existence of reasonable algorithms that generate empirical equivalents  should cast doubt on the existence of  such proofs.

 Does Guide-to-Lawhood follow from the metaphysical postulates of BSA? The answer is no. To see this, let us recall the comparison between $T_{M1}$ and $T_{M2}$. Following Guide-to-Lawhood, a Humean scientist living in a world with Maxwellian data would (and should) prefer $T_{M1}$ to $T_{M2}$ because the laws of $T_{M1}$ are simpler. However, it is metaphysically possible that the actual ontology does not include fields. If that is the actual mosaic, the best system may in fact correspond to the enormously complicated laws of $T_{M2}$. It follows that what counts as the actual best system on the BSA may differ from what we should accept as the best system according to Guide-to-Lawhood.

 There is no inconsistency, because \textit{what the laws are} can differ from \textit{what we should believe about what the laws are}.  Hence, defenders of BSA are in a similar epistemic situation as defenders of MinP. Even if the nomology of $T_{M2}$ represents the actual governing laws, a defender of MinP would and should regard $T_{M1}$ as more likely than $T_{M2}$. Humeans  and non-Humeans can be mistaken about the physical reality, even if they are completely rational. That is a feature and not a bug, because nomic realists should be fallible.

  This has ramifications for debates between Humeanism and non-Humeanism. According to an influential argument,\footnote{For example, see \cite{earman2005contact} and \cite{roberts2008law}.}  Humeanism has an epistemic advantage over non-Humeanism, because the former offers better epistemic access to the laws. The argument is that the Humean mosaic is all that we can empirically access, on which laws are supervenient, but non-Humeans postulate facts about laws that are empirically undecidable. But if the analysis in this paper is correct, such arguments are epistemically irrelevant. We never, in fact, occupy a position to observe everything in the mosaic. Our total evidence $E$ will never exhaust the entire mosaic $\xi$. But if both Humeans and non-Humeans need to accept an independent substantive epistemic posit in order to ensure epistemic access to the laws,  there is no real advantage on Humeanism. The reason we have epistemic access to laws is by appeal to this new principle of simplicity, which does not follow from the metaphysical posits of either Humeanism or non-Humeanism. Humeanism and non-Humeanism are epistemically on a par, with respect to the discovery and the evaluation of laws.

\section{Conclusion}

Nomic realism can be epistemically risky, since it requires ampliative inferences to go beyond what the empirical evidence guarantees. However, the risk is no smaller on Humeanism than on non-Humeanism. We need to decide what the physical laws are, in the vast space of possible candidates, based on our finite and limited evidence about the universe. The principle of simplicity, as a fundamental epistemic guide to lawhood, encourages us to look in the direction of simpler laws. It vindicates nomic realism when there is empirical equivalence (at least in those cases discussed in the paper) and avoids probabilistic incoherence when there are nested theories. Simplicity is not a simple thing, but from this analysis we can conclude that its connection to lawhood is much tighter than its connection to mere truth. Rather than being the seal of the true,  simplicity should be regarded as an epistemic guide to the laws.

\section*{Acknowledgement}

I thank Emily Adlam, James Brown, Weixin Cai, Craig Callender, Eugene Chua, Maaneli Derakhshani, Frederick Eberhardt, Sheldon Goldstein, Bill Harper, Christopher Hitchcock, Mahmoud Jalloh, Mario Hubert, Kerry McKenzie, Wayne Myrvold,  Francisco Pipa, Carlo Rovelli, Charles Sebens, Chris Smeenk, Kyle Stanford, Elliott Sober, Anncy Thresher,  Shimin Zhao, and audiences at Western Ontario and CalTech for helpful discussions, and especially Shelly Yiran Shi for her insightful suggestions and research assistance. This project is supported by an Academic Senate Grant from the University of California San Diego.