Optimal Sparse Kernel Learning for Hyperspectral Anomaly Detection
In this paper, a novel framework of sparse kernel learning for Support Vector Data Description (SVDD) based anomaly detection is presented. In this work, optimal sparse feature selection for anomaly detection is first modeled as a Mixed Integer Programming (MIP) problem. Due to the prohibitively high computational complexity of the MIP, it is relaxed into a Quadratically Constrained Linear Programming (QCLP) problem. The QCLP problem can then be practically solved by using an iterative optimization method, in which multiple subsets of features are iteratively found as opposed to a single subset. The QCLP-based iterative optimization problem is solved in a finite space called the Empirical Kernel Feature Space (EKFS) instead of in the input space or Reproducing Kernel Hilbert Space (RKHS). This is possible because of the fact that the geometrical properties of the EKFS and the corresponding RKHS remain the same. Now, an explicit nonlinear exploitation of the data in a finite EKFS is achievable, which results in optimal feature ranking. Experimental results based on a hyperspectral image show that the proposed method can provide improved performance over the current state-of-the-art techniques.
paper_main.tex
% Template for WHISPERS-2009 paper; to be used with:
%          stywhispers.sty  - WHISPERS LaTeX style file, and
%          IEEEbib.bst - IEEE bibliography style file.
% --------------------------------------------------------------------------
\documentclass{article}
\usepackage{stywhispers,amsmath,epsfig,graphicx}
\usepackage{ctable}
\usepackage{algorithmic, algorithm}
\usepackage{amsmath,amssymb,graphicx,verbatim,enumerate}

% Example definitions.
% --------------------
\def\x{{\mathbf x}}
\def\L{{\cal L}}

% Title.
% ------
\title{Optimal Sparse Kernel Learning for Hyperspectral Anomaly Detection}
%
% Single address.
% ---------------
%\name{Prudhvi Gurram, Heesung Kwon\thanks{}}
%\address{U.S. Army Research Laboratory, ATTN: RDRL-SES-E\\
%	2800 Powder Mill RD, Adelphi, Maryland 20783}
%%
% For example:
% ------------
%\address{School\\
%	Department\\
%	Address}
%
% Two addresses (uncomment and modify for two-address case).
% ----------------------------------------------------------
\twoauthors
  {Prudhvi Gurram, Heesung Kwon
  %\sthanks{Thanks to XYZ agency for funding.}
  }
	{U.S. Army Research Laboratory\\
     ATTN: RDRL-SES-E\\
	2800 Powder Mill RD\\
    Adelphi, Maryland 20783}
  {Zhimin Peng, Wotao Yin %\sthanks{The fourth author performed the work
	%while at ...}
}
	{Rice University\\
	Department of Computational \\
and Applied Mathematics\\
	Houston, Texas 77005}
%
\begin{document}
%\ninept
%
\maketitle
%
\begin{abstract}
In this paper, a novel framework of sparse kernel learning for Support Vector Data Description (SVDD) based anomaly detection is presented. In this work, optimal sparse feature selection for anomaly detection is first modeled as a Mixed Integer Programming (MIP) problem. Due to the prohibitively high computational complexity of the MIP, it is relaxed into a Quadratically Constrained Linear Programming (QCLP) problem.  The QCLP problem can then be practically solved by using an iterative optimization method, in which multiple subsets of features are iteratively found as opposed to a single subset. The QCLP-based iterative optimization problem is solved in a finite space called the \emph{Empirical Kernel Feature Space} (EKFS) instead of in the input space or \emph{Reproducing Kernel Hilbert Space} (RKHS). This is possible because of the fact that the geometrical properties of the EKFS and the corresponding RKHS remain the same. Now, an explicit nonlinear exploitation of the data in a finite EKFS is achievable, which results in optimal feature ranking. Experimental results based on a hyperspectral image show that the proposed method can provide improved performance over the current state-of-the-art techniques.
\end{abstract}
%
\begin{keywords}
Sparse kernel learning, Optimal feature selection, Empirical kernel feature space, Empirical kernel map
\end{keywords}
%
\section{Introduction}
\label{sec:intro}
Feature selection for learning algorithms aims to find a relevant subset of features that can improve the learning performance by discarding features not useful or even harmful for the given tasks. In the case of kernel-based anomaly detection, such as SVDD, the feature selection requires the accurate estimation of the contribution of each feature to the objective function, i.e., the radius of a hypersphere in the RKHS.

In this paper, a new framework of optimal sparse kernel learning for SVDD-based anomaly detection (OSKLAD) is proposed. The proposed OSKLAD optimally extends the feature selection technique used for the kernel-based learning approaches \cite{Tsang} into SVDD-based anomaly detection by fully optimizing the feature selection method for nonlinear kernels in a newly defined finite space called the EKFS \cite{learnKernel}. Hence, the OSKLAD can be considered as a fully optimized version of the wrapper approach to the SVDD-based anomaly detection with nonlinear kernels. The initial objective of the proposed OSKLAD begins with finding a single subset of original features that can be used to build an optimal hypersphere in the RKHS. This objective can be modeled as a Mixed Integer Programming (MIP) problem. However, the MIP problem is NP-hard, and so the MIP model is relaxed into a Quadratically Constrained Linear Programming (QCLP) problem \cite{qclp} by converting the objective function of the MIP problem into lower bounded quadratic inequality constraints. This QCLP problem is yet intractable due to the prohibitively large number of the inequality constraints. %In fact, the number of the inequality constraints is same as the number of all the possible combinations of the original features.
To address this issue, a cutting plane method based on the \emph{restricted master problem} coupled with Multiple Kernel Leaning (MKL) \cite{Rako2008} is iteratively used. The goal is to find only a small subset of the inequality constraints that are actively used to define the feasible region of the parameters of the given QCLP problem.
%The \emph{restricted master problem} basically iteratively eliminates irrelevant inequality constraints except those \emph{active} constraints.

The \emph{active} constraints are effectively identified by finding the \emph{most violating constraints} instead whose half-planes maximally violate the corresponding inequality constraints. Therefore, the task becomes finding multiple subsets of \emph{most violated features} associated with the corresponding \emph{most violating constraints} given the objective function, such as the radius of a hypersphere in the RKHS. However, finding the most violating constraints also becomes a combinatorial problem, if nonlinear kernels, such as Gaussian RBF kernel or high order polynomial kernels, are used, due to the prohibitively large number of possible combinations (subsets) of the original features. To tackle this issue, in the proposed OSKLAD, the most violated features are found in the EKFS. The EKFS is a finite space linearly spanned by basis vectors, which are generated by a map, called the Empirical Kernel Map (EKM). It is shown that the EKHS and the corresponding RKHS constructed by using the same kernel function have the same geometrical property. This means that solutions of any optimization problem obtained from either space are identical. In the proposed OSKLAD, the subsets of the most violated features are optimally found in the EKFS since individual feature ranking in terms of contribution to the radius in the EKFS can be performed optimally based on the property of canonical dot product and the finite dimensionality of the space.

%in which each kernel is optimally designed based on a sparse subset of features obtained in a newly generated space called the empirical kernel feature space\cite{learnKernel} is presented. The feature selection in the proposed work is performed in the finite empirical feature space, which is linearly spanned by the empirical kernel map with respect to training data coupled with any positive definite kernel. Canonical dot product can be endowed to the empirical kernel feature space by whitening the space\cite{learnKernel}. Therefore, based on the property of the canonical dot product, linear feature selection can be optimally performed in the finite-dimensional empirical kernel feature space leading to optimal selection of corresponding infinite dimensional RKHS. This is equivalent to optimal nonlinear selection of original features in the input space that would have generated those corresponding RKHS. This technique is optimal since the newly mapped features in the empirical kernel feature space can be individually ranked in an optimal way.

%The rest of the paper will be organized as follows. Section II describes the proposed OSKLAD. Section III provides the detail of how the features are selected in the EKFS. Section IV provides some simulation results, including one class classification data set and hyperspectral image data. Section V concludes the paper with some remarks about the proposed method.

\section{Optimal Sparse Kernel Learning}
In this section, we present an optimal sparse kernel learning for anomaly detection (OSKLAD) using SVDD as a basic building block. Inspired by the feature selection approach for the kernel-based classification \cite{Tsang}, the OSKLAD addresses the problem of the optimal feature selection for the SVDD-based anomaly detection. %The major drawback of the previous feature selection approach \cite{Tsang} is that it is only optimal up to linear kernel. OSKLAD tackles the optimality issue associated with nonlinear kernels and is fully optimal with both linear and nonlinear kernels. %OSKLAD follows a bottom-up approach starting with a single kernel with an optimal subset of features. More kernels (again with optimal feature subsets) are added in successive iterations as required, in order to obtain the final optimal kernel. The kernels are associated with the corresponding RKHS, in which the normalcy data is optimally described by the smallest enclosing hypersphere.
The basic formulation of OSKLAD  is to minimize the radius of the enclosing hypersphere while allowing outliers except that in OSKLAD, only a subset of features is used. So, the model is described as a mixed integer programming problem:
\begin{equation}\label{equ:SFSVDD}
    \begin{aligned}
       \min_{\mathbf{d}} \min_{R, \xi_i, \mathbf{a}}  ~ & R^2 + C \cdot \sum_{i=1}^{N} \xi_i\\
        \text{subject to} ~ & \| \Phi(\tilde{\textbf{x}}_i)  - \mathbf{a} \|^{2} \leq R^2 + \xi_i \\
        & \xi_i \geq 0 \\
        & \tilde{\textbf{x}}_i = \textbf{x}_i \odot \textbf{d}, ~  i =1,2,...,N,
    \end{aligned}
\end{equation}
where $\textbf{d}\in \mathbb{D} = \{\textbf{d}| d_j \in \{0,1\},\sum_{j=1}^M \textbf{d}_j = B, j =1,2,...,M \}$, and $\odot$ represents elementwise product. % as indicated in Fig. \ref{Fig:PointWiseProduct}.
%\begin{figure}[!ht]
%\begin{center}
%    \includegraphics[width=2.2in]{figs/cubes.png}
%     \caption{Elementwise product}
%     \label{Fig:PointWiseProduct}
%\end{center}
%\end{figure}
Here $B$ is a threshold that controls the number of features that are selected.
%It can be set either to a certain integer for fixed number of features in each subset, or, to a threshold as a percentage of change in the radius of the enclosing hypersphere for variable length feature subsets.
If one assumes that $\mathbf{d}$ is fixed in Eq. \ref{equ:SFSVDD}, it turns into a continuous constrained optimization problem just like a standard SVDD. By applying the Langrange multipliers and KKT conditions to it, we can derive the dual problem (similar to standard SVDD) as:
\begin{equation}\label{equ:DualSSVDD}
    \begin{aligned}
        \min_{\mathbf{d}} \max_{\alpha_{i}} & \sum_{i=1}^{N} \alpha_i k(\tilde{\textbf{x}}_i,\tilde{\textbf{x}}_i) - \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i
        \alpha_j k(\tilde{\textbf{x}}_i,\tilde{\textbf{x}}_j) \\
        \text{subject to} & \sum_{i=1}^{N} \alpha_{i} = 1 \\
                   & 0 \leq \alpha_i \leq C \\
                   & \tilde{\textbf{x}}_i = \textbf{x}_i \odot \textbf{d}, ~  i =1,2,...,N.
    \end{aligned}
\end{equation}
However, one should notice that Eq. \ref{equ:DualSSVDD} is still a mixed interger programming (MIP) problem due to the last constraint, which is computationally expensive to solve. In order to solve this problem, it can be converted into a Quadratically Constrained Linear Programming (QCLP). %as follows:
%According to the minimax inequality theorem \cite{MinMax}, if we interchange the order of $\min_{\mathbf{d}}$ and $\max_{\alpha}$, then (\ref{equ:DualSSVDD}) can be lower bounded by
%\begin{equation}\label{equ:lbDualSSVDD}
%    \begin{aligned}
%        \max_{\alpha_{i}}\min_{\mathbf{d}} & \sum_{i=1}^{N} \alpha_i k(\tilde{\textbf{x}}_i,\tilde{\textbf{x}}_i) - \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i
%        \alpha_j k(\tilde{\textbf{x}}_i,\tilde{\textbf{x}}_j) \\
%        \text{subject to} & \sum_{i=1}^{N} \alpha_{i} = 1 \\
%                   & 0 \leq \alpha_i \leq C \\
%                   & \tilde{\textbf{x}}_i = \textbf{x}_i \odot \textbf{d}, ~  i =1,2,...,N.
%    \end{aligned}
%\end{equation}
We define $S(\alpha, \textbf{d})=\sum_{i=1}^{N}\alpha_i k(\tilde{\textbf{x}}_i,\tilde{\textbf{x}}_i)- \sum_{i,j=1}^{N}\alpha_i\alpha_j k(\tilde{\textbf{x}}_i,\tilde{\textbf{x}}_j)$, and introduce an additional parameter $t$ to obtain the QCLP equivalent of (\ref{equ:DualSSVDD}) as follows:
\begin{equation}\label{equ:QCLP}
    \begin{aligned}
        \max_{\textbf{a}, t}~ & t \\
         \text{subject to}  ~ & \sum_{i=1}^{N} \alpha_i = 1 \\
                            ~ & 0 \leq \alpha_i \leq C \\
                            ~ & t \leq S(\alpha, \mathbf{d}),~ \forall ~ \mathbf{d} \in D.
   \end{aligned}
\end{equation}
Though Eq. \ref{equ:QCLP} is convex, a large number of inequality constraints (last condition in Eq. \ref{equ:QCLP}) makes it impractical to be solved by existing techniques. The number becomes huge if the features reside in a high dimensional space. Note that not all the inequality constraints used in Eq. \ref{equ:QCLP} are actively used in defining the feasible region of the optimization problem. In fact, only a small number of the constraints are useful and directly used to solve the optimization problem. Therefore, an iterative algorithm can be used, in which instead of solving Eq. \ref{equ:QCLP} at once, an intermediate solution pair $(t,\alpha)$ is iteratively updated based on a limited subset of previously found active constraints.  This optimization problem is called the \emph{restricted master problem}, which is closely related to the cutting plane algorithm described in \cite{CutPlane}. The \emph{restricted master problem} consists of two steps \cite{Ye}: 1) $(t,\alpha)$ are optimized based on a previously found restricted subset $\mathcal{I}$ of features, which maximally violates the constraints; and 2) a new vector $\textbf{d}$ of the most violated features is obtained based on newly optimized  $(t,\alpha)$ in step 1 and added to the restricted subset $\mathcal{I} = \mathcal{I} \bigcup \textbf{d} $. These two steps are iterated until convergence \cite{Prudhvi2012OSKLAD}. Finding $\textbf{d}$ of the most violated features is detailed in the next subsection.

The intermediate solution pair $(t,\alpha)$ is now obtained from the following optimization problem
\begin{equation}\label{equ:QCLPRMP}
    \begin{aligned}
        \max_{\textbf{a}, t}~ & t \\
         \text{subject to}  ~ & \sum_{i=1}^{N} \alpha_i = 1, \\
                            ~ & 0 \leq \alpha_i \leq C, \\
                            ~ & t \leq S(\alpha, \textbf{d}^{l}),~ \textbf{d}^{l} \in \mathcal{I}.
   \end{aligned}
\end{equation}
Let $\mu_l \geq 0$ be the dual variable for each constraint in Eq. \ref{equ:QCLPRMP}. The Lagrangian of Eq. \ref{equ:QCLPRMP} can be written as:
\begin{equation}\label{equ:QCLPlg}
	\begin{aligned}
		L(t,\mu) = t +\sum_{l=1}^p \mu_{l} S(\alpha, \textbf{d}^{l}).
	\end{aligned}
\end{equation}
By setting $\frac{\partial L}{\partial t} = 0$, we have $\sum_{l=1}^p \mu_l = 1$. The Lagrangian $L(t,\mu)$, after applying this partial KKT condition, can be rewritten as $L(t,\mu)=\sum_{l=1}^p \mu_{l} S(\alpha, \textbf{d}^{l})$, which transforms (\ref{equ:QCLP}) to the following problem:
\begin{equation}\label{equ:SKAD}
    \begin{aligned}
        \max_{\alpha} \min_{\mu}~ &  \sum_{l=1}^p \mu_{l} S(\alpha, \textbf{d}^{l})\\
         \text{subject to}  ~ & \sum_{i=1}^{N} \alpha_i = 1 \\
                            ~ & 0 \leq \alpha_i \leq C ~ \text{for} ~ i=1,2...,N\\
                            ~ & \sum_{l=1}^{p} \mu_l = 1,  \mu_l \geq 0 ~ \text{for} ~ l=1,2...,p.
   \end{aligned}
\end{equation}
%The iterative algorithm to solve (\ref{equ:QCLP}) consists of two steps: \emph{Step 1} - $\mathbf{d}$ is obtained by finding the set of features that violates the last constraint in \ref{equ:QCLP} based on current $t$ and $\alpha$; \emph{Step 2} - based on the previously determined $\mathbf{d}$, $\alpha$ and $\mu$ are obtained by solving (\ref{equ:SKAD}). The optimal selection of maximally violating feature vectors $\mathbf{d}$ is detailed in the next subsection.
One can observe that can be solved using a two-step iterative process to obtain optimal sparse weights of individual kernels $\mu$ and optimal lagrange multipliers $\alpha^*$ (which define the support vectors or the enclosing hypersphere).

\section{Optimal Feature Selection: Finding Maximally Violating Features}
For updating $\mathbf{d}$, the features that maximally violate the last constraint in Eq. \ref{equ:QCLP} need to be determined. Since the goal of Eq. \ref{equ:QCLP} is to maximize $t$, and it is upper-bounded by $S(\alpha, \textbf{d})$ according to the constraint, the features that maximally violate this constraint will minimize $S(\alpha, \textbf{d})$. One has to solve the following optimization problem:
\begin{equation}\label{equ:updateD}
    \begin{aligned}
        \min_{\textbf{d}} & ~S(\alpha, \textbf{d})\\
        \text{subject to} & ~\sum_{i=1}^M d_i = B\\
                          & ~ d_i \in \{0,1\}.
    \end{aligned}
\end{equation}
In this section, we describe the method to find these feature vectors for both linear kernel and non-linear kernel.

\subsection{Linear Kernel}
If a linear kernel is used, since $k \left(\textbf{x}_i,\textbf{x}_j\right) = \left\langle \textbf{x}_i, \textbf{x}_j \right\rangle$, we have $S(\alpha, \textbf{d})=\sum_{j=1}^{M}d_j c_j$, where $c_j = \sum_{i=1}^N\alpha_i x_{ij}^2 + (\sum_{i=1}^N \alpha_i x_{ij})^2$. $S(\alpha, \textbf{d})$ is a linear function of $\textbf{d}$. Once we have optimal support vectors, the global solution of $\textbf{d}$ can be easily obtained by sorting $c_j$'s in ascending order and setting the first $B$ corresponding elements in $\textbf{d}$, $d_j$ to $1$ and the rest to $0$. Once the optimal feature subset is chosen for a kernel, optimal $\alpha$ and $\mu$ are updated by solving Eq. \ref{equ:SKAD}. These two steps are repeated until the algorithm converges.
%
%\begin{algorithm}
%\caption{OSKLAD with linear kernel}
%\label{Alg:SSVDD}
%\begin{algorithmic}[l]
%\item[1:] Initialized: $\alpha = \frac{1}{N}\mathbf{1}$, find the maximally violating feature subset $\textbf{d}$, and set $\mathcal{C}=\{d\}$.
%\item[2:] Run SKAD and obtain optimal $\alpha$ and $\mu$.
%\item[3:] Find the next maximally violated feature subset $\mathbf{d}$ and set $\mathcal{C}=\mathcal{C}\bigcup\{d\}$.
%\item[4:] Repeat step2 2-3 until convergence.
%\end{algorithmic}
%\end{algorithm}

\subsection{Non-linear Kernel}
If a Gaussian RBF kernel is used, $S(\alpha, \textbf{d})$ is not a linear function of $\textbf{d}$. We cannot solve the problem in Eq. \ref{equ:updateD} optimally because of the large number of combinations of features that have to be considered. So, the data is tranformed from infinte dimensional RKHS into another space called \emph{empirical kernel feature space} (EKFS) with finite dimensionality using \emph{empirical kernel map} (EKM). This will allow us to select subsets of features optimally while still preserving the nonlinear correlations among the features. For a given set of training data points $\{ \textbf{x}_i \}_{i=1}^{n}$, the map defined by
\begin{equation}
\Phi_n : \mathbb{R}^n \rightarrow \mathbb{R}^n \textrm{ } \text{where} \textrm{ } \textbf{x} \mapsto k \left( \cdot,\textbf{x} \right) = \left( k \left( \textbf{x}_1,\textbf{x} \right),\ldots,k \left( \textbf{x}_n,\textbf{x} \right) \right)^T
\label{eq:ekm}
\end{equation}
is called the EKM with respect to $\{\textbf{x}_i\}_{i=1}^{n}$ \cite{learnKernel}. However, the kernel function $k$ used to build kernel matrices in previous subsections cannot be represented using $\Phi_n$, since they do not form an orthonormal system. The dot product to use in the representation of $k$ is the not the canonical dot product in the EKFS $\mathbb{R}^n$. In order to turn $\Phi_n$ into a feature map associated with $k$, EKFS is endowed with a dot product $\left\langle \cdot,\cdot\right\rangle_n$ such that $k(\textbf{x}_i,\textbf{x}_j) = \left\langle \Phi_n \left ( \textbf{x}_i \right ), \Phi_n \left ( \textbf{x}_j \right ) \right\rangle_n$. After analyzing certain conditions using this equality as shown in \cite{learnKernel}, the dot product $\left\langle \cdot,\cdot\right\rangle_n$ can be converted to a canonical dot product by merely whitening the EKFS and using the new basis functions as features. It can be represented as
\begin{equation}
k(\textbf{x}_i,\textbf{x}_j) = \left\langle \Phi_n^w \left ( \textbf{x}_i \right ), \Phi_n^w \left ( \textbf{x}_j \right ) \right\rangle,
\label{eq:dotpro}
\end{equation}
where the feature map in whitened EKFS is given by
\begin{equation}
\Phi_n^w :\textrm{ } \textbf{x} \mapsto K^{-\frac{1}{2}} \left( k \left( \textbf{x}_1,\textbf{x} \right),\ldots,k \left( \textbf{x}_n,\textbf{x} \right) \right)^T.
\label{eq:wekm}
\end{equation}
where $K$ is the Gram matrix and $K_{i,j} = k(\textbf{x}_i,\textbf{x}_j)$.
%It can be seen that this map is very similar to performing kernel PCA feature extraction on the original RKHS and hence, is also called as kernel PCA map.
The kernel function in Eq. \ref{eq:dotpro} is used to build the kernel matrices in Eqs. \ref{equ:DualSSVDD}-\ref{equ:updateD}. Hence, the feature subset selection problem turns exactly into (\ref{equ:updateD}) (linear version) except for the fact that in this case the features are selected in EKFS. Similar to the OSKLAD with a linear kernel, the overall Optimal Sparse Kernel Learning for Anomaly Detection (OSKLAD) in the EKFS is described in Algorithm 1.

\begin{algorithm}
\caption{OSKLAD with nonlinear kernel}
\label{Alg:SSVDDNL}
\begin{algorithmic}[2]
\item[1:] Map the data points into the EKFS by using a certain kernel $k$
\item[2:] Initialized: $\alpha = \frac{1}{N}\mathbf{1}$, find the maximally violating feature subset $\textbf{d}$, and set $\mathcal{I}=\{\textbf{d}\}$.
\item[3:] Run SKAD based on the kernel matrices generated by $\mathcal{I}$ and optimize for $\alpha$ and $\mu$.
\item[4:] Find the next maximally violated feature subset $\mathbf{d}$ based on the current $\alpha$ and $\mu$ and set $\mathcal{I}=\mathcal{I}\bigcup\{d\}$.
\item[5:] Repeat steps 3-4 until convergence.
\end{algorithmic}
\end{algorithm}

\section{Simulation Results}
\label{sec:format}

In this section, the performance of OSKLAD is evaluated on a hyperspectral digital imagery collection experiment(HYDICE) image, which contains 30 small painted pannels located in the background. 
%A HYDICE imaging sensor generates 210 bands across the whole spectral range ($0.4 - 2.5 \mu m$), but we only use 150 bands by discarding water absorption and low signal-to-noise ratio bands. 
We chose a small patch (69 pixels $\times$ 10 pixels) as the background data set, which is used to obtain the radius $R$ and the center of the hypersphere. The distance of each test pixel in the image to the center of the hypersphere is determined. If the distance is greater than $R$, the pixel is considered as an anomaly, otherwise, it is a background pixel. In our experiments, the performance of SVDD, SKAD \cite{SKAD}\footnote{Sparse kernel-based anomaly detection (SKAD) has been developed by two of the current authors} and OSKLAD with both linear and Gaussian RBF kernels are compared with one another. For SVDD and SKAD, both linear and Gaussian RBF kernel are used in the input space. For OSKLAD with linear kernel, feature selection is performed in the input space. However, for OSKLAD with Gaussian RBF kernel, the input vector is first mapped into EKFS using EKM. At this point, we can just use linear kernel in EKFS, which translates to using Gaussian RBF kernel in the input space as described in the previous sections. The kernel bandwidth parameter is determined by implementing the minimax technique on randomly selected 10 regions of the image to represent the background as done in \cite{banerjee2006support}. The same value is used over all the test pixels in the image for all the algorithms.

The number of features used for each hypersphere of SKAD with both linear and Gaussian RBF kernel and OSKLAD with linear kernel is 75, which is half of the total number of features. For OSKLAD in the EKFS, the total number of features available after mapping the pixels from input space to EKFS is reduced to 96, and we have used 48 features for each hypersphere. Fig.\ref{fig:res} shows the anomaly detection results for SVDD, SKAD and OSKLAD with both linear and Gaussian RBF kernels. The value of each pixel in the results is the ratio of the distance between the pixel and the radius of the hypersphere. For comparison, we normalize the scaled in all the resulting images to be between 0 and 1. One can see that all the six methods are able to identify the first two rows of anomalies, but OSKLAD in EKFS can identifies anomalies with much less noise (clean background) and it is also able to detect the small targets in the third row.

\begin{figure}[htb]
\begin{minipage}[b]{.48\linewidth}
  \centering
 \centerline{\epsfig{figure=figs/SVDD_linear_patch_2.png,width=3.0cm}}
  %\vspace{1.5cm}
  \centerline{(a) SVDD -- linear kernel}\medskip
\end{minipage}
\hfill
\begin{minipage}[b]{0.48\linewidth}
  \centering
 \centerline{\epsfig{figure=figs/SVDD_RBF_patch_2.png,width=3.0cm}}
  %\vspace{1.5cm}
  \centerline{(b) SVDD -- RBF kernel}\medskip
\end{minipage}
\begin{minipage}[b]{.48\linewidth}
  \centering
 \centerline{\epsfig{figure=figs/SKAD_linear_patch_2.png,width=3.0cm}}
  %\vspace{1.5cm}
  \centerline{(c) SKAD -- linear kernel}\medskip
\end{minipage}
\hfill
\begin{minipage}[b]{0.48\linewidth}
  \centering
 \centerline{\epsfig{figure=figs/SKAD_RBF_patch_2.png,width=3.0cm}}
  %\vspace{1.5cm}
  \centerline{(d) SKAD -- RBF kernel}\medskip
\end{minipage}
\begin{minipage}[b]{.48\linewidth}
  \centering
 \centerline{\epsfig{figure=figs/OSKLAD_linear_patch_2.png,width=3.0cm}}
 % \vspace{1.5cm}
  \centerline{(e) OSKLAD -- linear kernel}\medskip
\end{minipage}
\hfill
\begin{minipage}[b]{0.48\linewidth}
  \centering
 \centerline{\epsfig{figure=figs/OSKLAD_EKFS_patch_2.png,width=3.0cm}}
 % \vspace{1.5cm}
  \centerline{(f) OSKLAD -- EKFS}\medskip
\end{minipage}
\caption{Anomaly detection results of the HYDICE image using SVDD, SKAD and OSKLAD}
\label{fig:res}
%
\end{figure}

%One can also observe the advantages of OSKLAD in EKFS from the detection results for one of the targets in Fig.\ref{fig:mesh}. OSKLAD helps in generating a higher pick (around 150) of the ratio compared to the other 5 methods. Higher pick will be helpful for deciding which pixel should be considered as anomaly.

%\begin{figure}[htb]
%\begin{minipage}[b]{.3\linewidth}
%  \centering
% \centerline{\epsfig{figure=figs/mesh1.png,width=2.6cm}}
%  %\vspace{1.5cm}
%  \centerline{(a) SVDD--linear}\medskip
%\end{minipage}
%\hfill
%\begin{minipage}[b]{0.3\linewidth}
%  \centering
% \centerline{\epsfig{figure=figs/mesh3.png,width=2.6cm}}
%  %\vspace{1.5cm}
%  \centerline{(b) SKAD--linear}\medskip
%\end{minipage}
%\hfill
%\begin{minipage}[b]{.3\linewidth}
%  \centering
% \centerline{\epsfig{figure=figs/mesh5.png,width=2.6cm}}
%  %\vspace{1.5cm}
%  \centerline{(c) OSKLAD--linear}\medskip
%\end{minipage}


%\begin{minipage}[b]{.3\linewidth}
%  \centering
% \centerline{\epsfig{figure=figs/mesh2.png,width=2.6cm}}
%  %\vspace{1.5cm}
%  \centerline{(a) SVDD--RBF}\medskip
%\end{minipage}
%\hfill
%\begin{minipage}[b]{0.3\linewidth}
%  \centering
% \centerline{\epsfig{figure=figs/mesh4.png,width=2.6cm}}
%  %\vspace{1.5cm}
%  \centerline{(b) SKAD--RBF}\medskip
%\end{minipage}
%\hfill
%\begin{minipage}[b]{.3\linewidth}
%  \centering
% \centerline{\epsfig{figure=figs/mesh6.png,width=2.6cm}}
%  %\vspace{1.5cm}
%  \centerline{(c) OSKLAD--EKFS}\medskip
%\end{minipage}
%%
%\caption{Three dimensional plot of one target by SVDD, SKAD and OSKLAD}
%\label{fig:mesh}
%%
%\end{figure}

%Table \ref{tab:KernelNumber} shows the initial number of kernels that we set to SKAD and OSKLAD as well as the final number
%and final number with nonzero weight of kernels to construct the hypersphere. As can be observed from Table \ref{tab:KernelNumber}, OSKLAD in EKFS uses far less number of kernels than SKAD after optimization but still provides much superior detection performance than SKAD. The number of iterations required by OSKLAD to converge is also very small since it equals to the number of kernels, which helps in making the training process fast.
%\begin{table}[!ht]
%\label{tab:KernelNumber}
%\centering
%\caption{ Kernel Number}
%\begin{tabular}{ccccc}
%    \toprule
%    \multicolumn{1}{c}{} & \multicolumn{2}{c}{SKAD} & \multicolumn{2}{c}{OSKLAD} \\
%    \cmidrule(r){2-5}
%    Kernel &  Linear & RBF & Linear &  EKFS\\
%    \midrule
%    Initial  &  50      & 50      & 50  &  50 \\
%    Final  &   50     &  50     & 6     &   6 \\
%    Final (nonzero weight) &  43     & 44     & 4     &   5 \\
%    \bottomrule
%    \end{tabular}
%\end{table}


\section{Conclusions}
In the proposed work, to achieve optimality in kernel-based feature selection for anomaly detection using SVDD, the QCLP problem is optimally solved in a new finite space called the Empirical Kernel Feature Space (EKFS) instead of the RKHS. Experimental result show that by optimally selecting features, significant improvements can be made in hyperspectral anomaly detection in EKFS rather than the original input space.




% Below is an example of how to insert images. Delete the ``\vspace'' line,
% uncomment the preceding line ``\centerline...'' and replace ``imageX.ps''
% with a suitable PostScript file name.
% -------------------------------------------------------------------------



% References should be produced using the bibtex program from suitable
% BiBTeX files (here: strings, refs, manuals). The IEEEbib.bst bibliography
% style file from IEEE produces unsorted bibliography list.
% -------------------------------------------------------------------------
\bibliographystyle{IEEEbib}
\bibliography{strings,myref}

\end{document}

myref.bbl
 \newcommand{\noop}[1]{}
\begin{thebibliography}{1}

\bibitem{Tsang}
M.~Tan, L.~Wang, and I.~W. Tsang,
\newblock ``Learning sparse {SVM} for feature selection on very high
  dimensional datasets,''
\newblock in {\em ICML}, Haifa, Israel, June 2010, pp. 1047--1054.

\bibitem{learnKernel}
B.~Sch\"{o}lkopf and A.~J. Smola,
\newblock {\em Learning with Kernels},
\newblock The MIT Press, Massachusetts, 2002.

\bibitem{qclp}
R.~Hettich and K.~O. Kortanek,
\newblock ``Semi-infinite programming: Theory, methods, and applications,''
\newblock {\em {SIAM} Review}, vol. 35, no. 3, pp. 380--429, Sept. 1993.

\bibitem{Rako2008}
A.~Rakotomamonjy, F.~R. Bach, S.~Canu, and Y.~Grandvalet,
\newblock ``Simplemkl,''
\newblock {\em J. Machine Learning Research}, vol. 9, pp. 2491--2521, 2008.

\bibitem{CutPlane}
J.~E. Kelly,
\newblock ``The cutting plane method for solving convex problems,''
\newblock {\em J. Soc. Indust. Appl. Math.}, vol. 8, no. 4, Dec. 1960.

\bibitem{Ye}
J.~Chen and J.~Ye,
\newblock ``Training {SVM} with indefinite kernels,''
\newblock in {\em ICML}, Helsinki, June 2008, pp. 136--143.

\bibitem{Prudhvi2012OSKLAD}
P.~Gurram, Z.~Peng, H.~Kwon, and W.~Yin,
\newblock ``Optimal sparse kernel learning for anomaly detection,''
\newblock {\em Pattern Recognition}, \noop{2012}under review.

\bibitem{SKAD}
P.~Gurram, H.~Kwon, and T.~Han,
\newblock ``Sparse kernel-based hyperspectral anomaly detection,''
\newblock vol. 9, no. 5, pp. 943--947, Sept. 2012.

\bibitem{banerjee2006support}
Amit Banerjee, Philippe Burlina, and Chris Diehl,
\newblock ``A support vector method for anomaly detection in hyperspectral
  imagery,''
\newblock {\em Geoscience and Remote Sensing, IEEE Transactions on}, vol. 44,
  no. 8, pp. 2282--2291, 2006.

\end{thebibliography}

paper_main.bbl
 \newcommand{\noop}[1]{}
\begin{thebibliography}{1}

\bibitem{Tsang}
M.~Tan, L.~Wang, and I.~W. Tsang,
\newblock ``Learning sparse {SVM} for feature selection on very high
  dimensional datasets,''
\newblock in {\em ICML}, Haifa, Israel, June 2010, pp. 1047--1054.

\bibitem{learnKernel}
B.~Sch\"{o}lkopf and A.~J. Smola,
\newblock {\em Learning with Kernels},
\newblock The MIT Press, Massachusetts, 2002.

\bibitem{qclp}
R.~Hettich and K.~O. Kortanek,
\newblock ``Semi-infinite programming: Theory, methods, and applications,''
\newblock {\em {SIAM} Review}, vol. 35, no. 3, pp. 380--429, Sept. 1993.

\bibitem{Rako2008}
A.~Rakotomamonjy, F.~R. Bach, S.~Canu, and Y.~Grandvalet,
\newblock ``Simplemkl,''
\newblock {\em J. Machine Learning Research}, vol. 9, pp. 2491--2521, 2008.

\bibitem{CutPlane}
J.~E. Kelly,
\newblock ``The cutting plane method for solving convex problems,''
\newblock {\em J. Soc. Indust. Appl. Math.}, vol. 8, no. 4, Dec. 1960.

\bibitem{Ye}
J.~Chen and J.~Ye,
\newblock ``Training {SVM} with indefinite kernels,''
\newblock in {\em ICML}, Helsinki, June 2008, pp. 136--143.

\bibitem{Prudhvi2012OSKLAD}
P.~Gurram, Z.~Peng, H.~Kwon, and W.~Yin,
\newblock ``Optimal sparse kernel learning for anomaly detection,''
\newblock {\em Pattern Recognition}, \noop{2012}under review.

\bibitem{SKAD}
P.~Gurram, H.~Kwon, and T.~Han,
\newblock ``Sparse kernel-based hyperspectral anomaly detection,''
\newblock vol. 9, no. 5, pp. 943--947, Sept. 2012.

\bibitem{banerjee2006support}
Amit Banerjee, Philippe Burlina, and Chris Diehl,
\newblock ``A support vector method for anomaly detection in hyperspectral
  imagery,''
\newblock {\em Geoscience and Remote Sensing, IEEE Transactions on}, vol. 44,
  no. 8, pp. 2282--2291, 2006.

\end{thebibliography}
