Active Sample Learning and Feature Selection: A Unified Approach
{Changsheng Li
%% You can go ahead and credit any number of authors here
%% e.g. one 'row of three' or two rows (consisting of one row of three %% and a second row of one
two or three). %% %% The command \alignauthor (no curly braces needed) should %% precede each author name
affiliation/snail-mail address and %% e-mail address. Additionally
tag each line of %% affiliation/address with \affaddr
and tag the %% e-mail address with \email. %% %% 1st. author %\alignauthor Changsheng Li
%\titlenote{Dr.~Trovato insisted his name be first.
This paper focuses on the problem of simultaneous sample and feature selection for machine learning in a fully unsupervised setting. Though most existing works tackle these two problems separately that derives two well-studied sub-areas namely active learning and feature selection, a unified approach is inspirational since they are often interleaved with each other. Noisy and high-dimensional features will bring adverse effect on sample selection, while `good' samples will be beneficial to feature selection. We present a unified framework to conduct active learning and feature selection simultaneously. From the data reconstruction perspective, both the selected samples and features can best approximate the original dataset respectively, such that the selected samples characterized by the selected features are very representative. Additionally our method is one-shot without iteratively selecting samples for progressive labeling. Thus our model is especially suitable when the initial labeled samples are scarce or totally absent, which existing works hardly address particularly for simultaneous feature selection. To alleviate the NP-hardness of the raw problem, the proposed formulation involves a convex but non-smooth optimization problem. We solve it efficiently by an iterative algorithm, and prove its global convergence. Experiments on publicly available datasets validate that our method is promising compared with the state-of-the-arts.
sig-alternate.tex
% This is "sig-alternate.tex" V2.0 May 2012
% This file should be compiled with V2.5 of "sig-alternate.cls" May 2012
%
% This example file demonstrates the use of the 'sig-alternate.cls'
% V2.5 LaTeX2e document class file. It is for those submitting
% articles to ACM Conference Proceedings WHO DO NOT WISH TO
% STRICTLY ADHERE TO THE SIGS (PUBS-BOARD-ENDORSED) STYLE.
% The 'sig-alternate.cls' file will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V2.5) produces:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'sig-alternate.cls' you have control, however, from within
% the source .tex file, over both the CopyrightYear
% (defaulted to 200X) and the ACM Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% e.g.
% \CopyrightYear{2007} will cause 2007 to appear in the copyright line.
% \crdata{0-12345-67-8/90/12} will cause 0-12345-67-8/90/12 to appear in the copyright line.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% ================= IF YOU HAVE QUESTIONS =======================
% Questions regarding the SIGS styles, SIGS policies and
% procedures, Conferences etc. should be sent to
% Adrienne Griscti (griscti@acm.org)
%
% Technical questions _only_ to
% Gerald Murray (murray@hq.acm.org)
% ===============================================================
%
% For tracking purposes - this is V2.0 - May 2012

\documentclass{sig-alternate}
\usepackage{color,url,subfigure}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{proposition}{Proposition}[section]
%\newtheorem{definition}{Definition}[section]
\newtheorem{claim}{Claim}[section]
\newtheorem{remark}{Remark}[section]

\begin{document}
%
% --- Author Metadata here ---
%\conferenceinfo{KDD}{'15 Hilton, Sydney Australia}
%\CopyrightYear{2007} % Allows default copyright year (20XX) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.
% --- End of Author Metadata ---

\title{Active Sample Learning and Feature Selection: A Unified Approach}

%\author{{Changsheng Li}$^\dag$, Xiangfeng Wang$\ddag$, Weishan Dong$\dag$, Junchi Yan$\tt\small^1$, Qingshan Liu$\tt\small^1$, Hongyuan Zha$\tt\small^1$\\
%$\tt\small^1$IBM Research-China, Beijing, China, 100094\\
%$\tt\small^2$CICE, Nanjing University of Information Science and Technology, Nanjing, China, 210044\\
%%%Institution1 address\\
%$\tt\small^1${\tt\small $\{$lcsheng, ylyang, mengfj, dongweis, yuwangbj, xujingm$\}@$cn.ibm.com}, $\tt\small^2$\tt\small qsliu$@$nuist.edu.cn}

\numberofauthors{5} %  in this sample file, there are a *total*
%% of EIGHT authors. SIX appear on the 'first-page' (for formatting
%% reasons) and the remaining two appear in the \additionalauthors section.
%%
\author{
%% You can go ahead and credit any number of authors here,
%% e.g. one 'row of three' or two rows (consisting of one row of three
%% and a second row of one, two or three).
%%
%% The command \alignauthor (no curly braces needed) should
%% precede each author name, affiliation/snail-mail address and
%% e-mail address. Additionally, tag each line of
%% affiliation/address with \affaddr, and tag the
%% e-mail address with \email.
%%
%% 1st. author
%\alignauthor
Changsheng Li\\
%\titlenote{Dr.~Trovato insisted his name be first.}\\
       \affaddr{IBM Research-China}\\
       \affaddr{Beijing, China}\\
       \email{lcsheng@cn.ibm.com}
% 2nd. author
\alignauthor
Xiangfeng Wang\\
%\titlenote{The secretary disavows any knowledge of this author's actions.}\\
       \affaddr{East China Normal University}\\
       \affaddr{Shanghai, China}\\
       \email{xfwang@sei.ecnu.edu.cn}
% 3rd. author
\alignauthor
Weishan Dong\\
%\titlenote{This author is the one who did all the really hard work.}\\
       \affaddr{IBM Research-China}\\
       \affaddr{Beijing, China}\\
       \email{dongweis@cn.ibm.com}
\and  % use '\and' if you need 'another row' of author names
% 4th. author
\alignauthor Junchi Yan\\
       \affaddr{Shanghai Jiao Tong University}\\
       \affaddr{Shanghai, China}\\
       \email{yanjc@cn.ibm.com }
\alignauthor Qingshan Liu\\
       \affaddr{Nanjing University of Information Science and Technology}\\
       %\affaddr{Nanjing, China}\\
       \email{qsliu@nuist.edu.cn}
\alignauthor Hongyuan Zha\\
      \affaddr{Georgia Institute of Technology}\\
       \affaddr{Atlanta, USA}\\
       \email{zha@cc.gatech.edu}
%% 5th. author
%% 6th. author
%%\alignauthor Charles Palmer\\
%%       \affaddr{Palmer Research Laboratories}\\
%%       \affaddr{8600 Datapoint Drive}\\
%%       \affaddr{San Antonio, Texas 78229}\\
%%       \email{cpalmer@prl.com}
}

\maketitle
\begin{abstract}
This paper focuses on the problem of simultaneous sample and feature selection for machine learning in a fully unsupervised setting. Though most existing works tackle these two problems separately that derives two well-studied sub-areas namely active learning and feature selection, a unified approach is inspirational since they are often interleaved with each other. Noisy and high-dimensional features will bring adverse effect on sample selection, while `good' samples will be beneficial to feature selection.
We present a unified framework to conduct active learning and feature selection simultaneously. From the data reconstruction perspective, both the selected samples and features can best approximate the original dataset respectively, such that the selected samples characterized by the selected features are very representative. Additionally our method is one-shot without iteratively selecting samples for progressive labeling. Thus our model is especially suitable when the initial labeled samples are scarce or totally absent, which existing works hardly address particularly for simultaneous feature selection.
To alleviate the NP-hardness of the raw problem, the proposed formulation involves a convex but non-smooth optimization problem. We solve it efficiently by an iterative algorithm, and prove its global convergence. Experiments on publicly available datasets validate that our method is promising compared with the state-of-the-arts.
\end{abstract}

% A category with the (minimum) three required fields
\category{H.2.8}{Database Management}{Database Applications}[data mining]
%A category including the fourth, optional field follows...
\category{I.2.6}{Artificial Intelligence}{Learning}

%\terms{Algorithm}

\keywords{Active learning, feature selection, matrix factorization}
\section{INTRODUCTION}
In many real-life machine learning tasks, unlabeled data is often easily available whereas labeled data is scarce.
In order to build powerful predictive models, one usually requires domain experts to manually annotate samples, but this is an expensive and time-consuming procedure.
Active learning \cite{freund1997selective} provides a means to alleviate this problem by carefully selecting samples to be labeled by experts.
Typically, the active learning algorithms prefer to query those unlabeled samples which can improve the prediction performance the most if they were labeled and used as training data.
In this way, the active learner aims to pick out as few samples as possible to label for minimizing the total annotating cost, while an accurate supervised learning model can be built based on these labeled data.

Many active learning algorithms have been proposed \cite{cohn1996active,roy2001toward,huang2010active,li2012multi} in the past decade.
There are two main group methods for selecting unlabeled samples to label \cite{wang2013querying}: One is to select the most informative samples, such as uncertainty sampling \cite{lewis1994sequential}, query by committee \cite{freund1997selective}, and empirical risk minimization \cite{roy2001toward}.
These algorithms are implemented iteratively, where a model is learned with the existing labeled data and new samples are chosen to be labeled based on the learned model.
Since training model usually needs a large number of labeled data to avoid the samples bias, the above methods should be used after sufficient labeled samples are collected \cite{nie2013early}.
The other group aims at querying the most representative samples from a perspective of data reconstruction \cite{yu2006active,Chattopadhyay2012,cai2012manifold,nie2013early,hu2013active}.
Different from the first group, methods in this group are one-shot and non-iterative for selecting samples.
Such active learning methods are usually applied when there is no initial labeled data.

Although active learning has been well studied for years, it still has some issues in many real-world scenarios. For example, the sample is often characterized by high-dimensional features, and some of features are often noisy or irrelevant. These noisy or irrelevant features bring adverse influence on selecting informative or representative samples. Moreover, after querying samples, some supervised learning models, such as decision tree, are often trained based on these labeled data for various applications. However, high-dimensional features significantly increase the time and space requirements for model training. Meanwhile, when only limited labeled samples are available, it is difficult to guarantee reliable model parameter estimates in high-dimensional feature space. One may state that, if we apply some state-of-the-art feature selection techniques, such as $Q-\alpha$ \cite{wolf2005feature}, to learn a low-dimensional representation before active learning, these problems might be solved. Of course, this should be helpful for active learning to some extent, while common feature selection techniques and active learning algorithms are independent in designing, directly combining them usually cannot guarantee to obtain the optimal results. Therefore, it will benefit from devising principled model and algorithm for incorporating active learning and feature selection in a unified fashion. Recently, Raghavan et al. \cite{raghavan2006active} presented a method to use human feedback on both features and samples for active learning. Kong et al. \cite{kong2011dual} proposed a dual feature selection and sample selection method in the context of graph classification.
Bilgic \cite{bilgic2012combining} proposed a dynamic dimensionality reduction algorithm that determined the appropriate number of dimensions for each active learning iteration.
Since all of the above three algorithms are implemented iteratively, and need to train models for querying in each iteration, they are suitable to work in the scenarios of the first group active learning methods. Different from them, we focus on learning important features for the second group active learning algorithms, i.e., in the case when no initial labeled samples are available. This is an unsupervised learning problem, which is much harder due to the absence of labels that would guide the search for relevant information.

In this paper, we present a unified view of (sampled based) \underline{A}ctive \underline{L}earning and \underline{F}eature \underline{S}election, called ALFS, which is inspired by the approximation method for CUR matrix decomposition.

The main contributions of this paper are:
\begin{itemize}
\item[\romannumeral1)]
To our knowledge, this is the first work for presenting a unified view for one-shot active learning and feature selection, which is important for real-world applications, since it dispenses with any label effort unlike those progressive interactive labeling active learning methods.
\item[\romannumeral2)]
This work is the first one to formulate and build the natural connection between CUR decomposition and simultaneous sample and feature selection.
\item[\romannumeral3)]
 We devise a novel model and convex optimization algorithm to solve the one-shot sample and feature learning problem.
\item[\romannumeral4)]
 The convergence of the proposed iterative algorithm is theoretically proved, and extensive empirical results demonstrate the advantages of our approach.
\end{itemize}

%In this paper, we propose a novel method to integrate \underline{A}ctive \underline{L}earning and \underline{F}eature \underline{S}election in a unified framework, named as ALFS.
%Specifically, we take advantage of CUR matrix decomposition \cite{drineas2008relative} to find a representative feature subset and a representative instance subset simultaneously, such that the whole training dataset can be well approximated by them. Different from typical CUR decomposition taking a randomized algorithmic approach, we propose a convex formulation using the structured sparsity-inducing norms to select the most representative features and instances.
%Moreover, we add a regularization term into the objective function to realize the local reconstruction of the data, which can make the selected features and instances more representative.
%Finally, a simple yet efficient iterative algorithm is designed to solve our non-smooth objective function, and its global convergence is proved.
%Extensive experiments are conducted on publicly available datasets, and the experimental results demonstrate the effectiveness of the proposed method in comparison with the
%state-of-the-art active learning methods.

The rest of this paper is organized as follows: we propose a unified framework to conduct active learning and feature selection simultaneously in section 2. Section 3 reviews related work on the second group active learning algorithms. The experimental results are reported in Section 4. Section 5 presents concluding remarks and future work.

{\bf Notations}.  In this paper, matrices are written as boldface uppercase letters and vectors are written as boldface lowercase letters.
Given a matrix $\mathbf{P}$, we denote its $(i,j)$-th entry, $i$-th row, $j$-th column as $\mathbf{P}_{ij}$, $\mathbf{p}^i$, $\mathbf{p}_j$, respectively. The only used vector norm is the $l_2$ norm, denoted by $\|\!\cdot\!\|_2$. A variety of norms on matrices will be used. The $l_1$, $l_{2,1}$, $l_\infty$ norms of a matrix are defined by $\|\mathbf{P}\|_1=\sum_{i,j}|\mathbf{P}_{ij}|$, $\|\mathbf{P}\|_{2,1}=\sum_{i=1}^n\sqrt{\sum_{j=1}^m\mathbf{P}_{ij}^2}=\sum_{i=1}^n\|\mathbf{p}^i\|_2$, and $\|\mathbf{P}\|_\infty=\max_{i,j}|\mathbf{P}_{ij}|$, respectively.
The quasi-norm $l_{2,0}$ norm of a matrix $\mathbf{P}$ is defined as the number of the nonzero rows of $\mathbf{P}$, denoted by $\|\mathbf{P}\|_{2,0}$.
The Frobenius norm and the nuclear norm (the summation of singular values of a matrix) are denoted by $\|\mathbf{P}\|_F$ and $\|\mathbf{P}\|_{\ast}$, respectively. The Euclidean inner product between two matrices is $\langle \mathbf{P},\mathbf{Q}\rangle= tr(\mathbf{P}^T\mathbf{Q})$,
where $\mathbf{P}^T$ is the transpose of the matrix $\mathbf{P}$ and $tr(\cdot)$ is the trace of a matrix. The rank of a matrix is denoted by $\text{rank}(\cdot)$.

\section{PROPOSED METHOD}
Given an unlabeled dataset $\mathbf{X}=[\mathbf{x}_1,\ldots,\mathbf{x}_n]\in \mathbb{R}^{d \times n}$, our goal is to pick out $m\ (m < n)$ samples for labeling by user, and simultaneously select $r\ (r < d)$ features as the new feature representation,  such that the potential performance is maximized when the model is trained based on the selected $m$ labeled samples under the new representation.
This is a more challenging problem than traditional representativeness based active learning problems, because selecting $m$ samples to best approximate $\mathbf{X}$ often leads to an NP-hard problem \cite{yu2006active}, and finding $r$ features as the most representative feature subset is also often NP-hard \cite{he2011variance}.

\subsection{Active Learning and Feature Selection via Matrix Decomposition}
Inspired by the CUR matrix decomposition \cite{boutsidis2014optimal}, we propose a unified framework to find the most representative samples and features.
To make this paper self-contained, we first introduce CUR matrix factorization.
\newtheorem{definition}{Definition}[section]
\begin{definition}\label{def1}
Given $\mathbf{X}\in \mathbb{R}^{d\times n}$ of rank $\rho$ = rank$(\mathbf{X})$, rank parameter $k<\rho$, and accuracy parameter $0 <\varepsilon < 1$, the CUR factorization for $\mathbf{X}$ aims to find $\mathbf{C}\in \mathbb{R}^{d\times m}$ with $m$ columns from $\mathbf{X}$, $\mathbf{R}\in \mathbb{R}^{r\times n}$ with $r$ rows of $\mathbf{X}$, and $\mathbf{U}\in \mathbb{R}^{m\times r}$, with $m$, $r$, and $rank(\mathbf{U})$ being as small as possible, such that $\mathbf{X}$ is reconstructed within relative-error:
\begin{align}\label{svd1}
\|\mathbf{X}-\mathbf{C}\mathbf{U}\mathbf{R}\|_F^2\leq (1+\varepsilon)\|\mathbf{X}-\mathbf{X}_k\|_F^2,
\end{align}
\end{definition}
where $\mathbf{X}_k=\mathbf{U}_k\Sigma_k\mathbf{V}_k^T\in \mathbb{R}^{d\times n}$ is the best rank $k$ matrix obtained via the SVD of $\mathbf{X}$.

From an algorithmic perspective, the matrices $\mathbf{C}$, $\mathbf{U}$, and $\mathbf{R}$ can be obtained by minimizing the approximation error $\|\mathbf{X}-\mathbf{C}\mathbf{U}\mathbf{R}\|_F^2$. Here we make a key observation that the above definition is closely related to the problem of simultaneous sample and feature selection, though to our surprise, existing works hardly point out or explore this connection to solve the active learning problem: on one hand, $\mathbf{UR}$ can be regarded as a reconstruction coefficient matrix, and $\mathbf{C}$ denotes the selected $m$ samples, thus minimizing $\|\mathbf{X}-\mathbf{C}\mathbf{U}\mathbf{R}\|_F^2$ means that the total reconstruction error is minimized, which can make the data points listed in $\mathbf{C}$ be the most representative.
The reconstruction coefficients $\mathbf{UR}$ are related to an $r$-dimensional feature subset of the dataset.
Actually, the reconstruction coefficients of each reconstructed data point $\mathbf{x}_i$ are formed by a linear combination of its $r$ features.
On the other hand, $\mathbf{CU}$ can be also regarded as a reconstruction coefficient matrix, and $\mathbf{R}$ is the new low-dimensional representation of $\mathbf{X}$, so minimizing $\|\mathbf{X}-\mathbf{C}\mathbf{U}\mathbf{R}\|_F^2$ also indicates that the selected $r$ features can represent the whole dataset most precisely. The construction of the coefficient matrix $\mathbf{CU}$ depends on a sample subset of $\mathbf{X}$.
Clearly, active learning and feature selection can be conducted simultaneously in such a joint framework via CUR factorization.

Despite the above connection from CUR decomposition to feature selection and active learning, the original CUR formulation and its existing solvers can not be directly applied to solve the simultaneous feature and sample selection task due to the under-determination of a general CUR model. In the context of active sample/feature learning, this paper proposes a tailored objective function rooted from CUR decomposition, while being more informative by adding regularization terms to incorporate prior knowledge. Moreover, unlike most existing CUR solvers being randomized or heuristic algorithms \cite{mahoney2009cur,boutsidis2014optimal}, we utilize the structured sparsity-inducing norms to relax the objective from a non-convex optimization problem to a convex one, which allows for devising an efficient variant of the alternating direction method of multipliers (ADMM) \cite{gabay1976dual}.

\subsection{A Convex Formulation}
Let $\mathbf{p}=(p_1,\ldots,p_n)^T\in \{0,1\}^n$ and $\mathbf{q}=(q_1,\ldots,q_d)^T\in \{0,1\}^d$ denote two indicator variables to represent whether a sample and a feature is selected or not, respectively. $p_i=1$ (or 0) indicates that the $i$-th sample is selected (or not), and $q_i=1$ (or 0) means that the $i$-th feature is selected (or not). Minimizing $\|\mathbf{X}-\mathbf{C}\mathbf{U}\mathbf{R}\|_F^2$ can be re-written as:
\begin{align}\label{obj1}
\min\limits_{\mathbf{p},\mathbf{q},\widehat{\mathbf{U}}\in \mathbb{R}^{n\times d}}\ &\|\mathbf{X}-\mathbf{X}\text{diag}(\mathbf{p})\widehat{\mathbf{U}}\text{diag}(\mathbf{q})\mathbf{X}\|_F^2\nonumber\\
s.t. \ &\mathbf{1}_n^T\mathbf{p}=m, \mathbf{p}\in \{0,1\}^n,\\
&\mathbf{1}_d^T\mathbf{q}=r, \mathbf{q}\in \{0,1\}^r,\nonumber
\end{align}
where $\text{diag}(\mathbf{p})$ is a diagonal matrix with its diagonal elements being $\mathbf{p}$, and $\mathbf{1}_n$ is an $n$-dimensional vector with all components being 1. $\mathbf{X}\text{diag}(\mathbf{p})$ in (\ref{obj1}) aims to make $m$ columns of $\mathbf{X}$ unchanged, and reset the rest $n-m$ columns to zero vectors. $\text{diag}(\mathbf{q})\mathbf{X}$ tends to keep $r$ rows of $\mathbf{X}$ unchanged, and reset the rest $(d-r)$ rows to zero vectors.

Using the matrix $l_{2,0}$ norm, we formulate the problem in (\ref{obj1}) as:
\begin{align}\label{obj2}
&\min\limits_{\mathbf{W}\in \mathbb{R}^{n\times d}} \ \|\mathbf{X}-\mathbf{XWX}\|_F^2\nonumber\\
s.t. \ &\|\mathbf{W}\|_{2,0}=m, \|\mathbf{W}^T\|_{2,0}=r,
\end{align}
where $\mathbf{W}=\text{diag}(\mathbf{p})\widehat{\mathbf{U}}\text{diag}(\mathbf{q}).$

In Definition \ref{def1}, the rank of the matrix $\mathbf{U}$ should be as small as possible. Based on this point and (\ref{obj2}), we propose to optimize the following objective function:
\begin{align}\label{obj3}
\min\limits_{\mathbf{W}\in \mathbb{R}^{n\times d}} \ &\|\mathbf{X}-\mathbf{XWX}\|_F^2+\alpha\|\mathbf{W}\|_{2,0}+\beta\|\mathbf{W}^T\|_{2,0}\nonumber\\
&+\gamma \text{rank}(\mathbf{W}),
\end{align}
where $\alpha\geq 0$, $\beta\geq 0$, and $\gamma\geq 0$ are three regularization parameters. The first three terms in (\ref{obj3}) aim to select a sample subset and a feature subset to minimize the reconstruction error. The last term purposes to make $\mathbf{W}$ be a low-rank matrix.

However, (\ref{obj3}) is still an NP-hard problem due to the matrix $l_{2,0}$ norm and the combinational nature of the rank function.
Fortunately, there exists theoretical progress that $\|\mathbf{W}\|_{2,1}$ is the minimum convex hull of $\|\mathbf{W}\|_{2,0}$ \cite{nie2013early}.
The result of minimizing $\|\mathbf{W}\|_{2,1}$ is the same as that of minimizing $\|\mathbf{W}\|_{2,0}$, as long as $\mathbf{W}$ is row-sparse enough.
Meanwhile, it has been proved that the convex envelope of rank($\mathbf{W}$) on the set \{$\mathbf{W}\in \mathbb{R}^{n\times d}: \sigma_1(\mathbf{W})\leq 1$\} is the nuclear norm $\|\mathbf{W}\|_{\ast}$ \cite{fazel2002matrix}, where $\sigma_1(\mathbf{W})$ is the largest singular value of $\mathbf{W}$.
In other words, the nuclear norm is the best convex approximation of the rank function over the unit ball of matrices with the largest singular values less than one.
Therefore, (\ref{obj3}) can be relaxed to the following convex optimization problem:
\begin{align}\label{obj4}
\min\limits_{\mathbf{W}\in \mathbb{R}^{n\times d}} \ &\|\mathbf{X}-\mathbf{XWX}\|_F^2+\alpha\|\mathbf{W}\|_{2,1}+\beta\|\mathbf{W}^T\|_{2,1}\nonumber\\
&+\gamma \|\mathbf{W}\|_{\ast}.
\end{align}

\subsection{Local Linear Reconstruction}
In the new objective function (\ref{obj4}), we can see that each data point is reconstructed by a linear combination of all the selected points (when the $i$-th row of the reconstruction coefficient matrix $\mathbf{WX}$ in (\ref{obj4}) is not a zero vector, $\mathbf{x}_i$ is chosen as one of the most representative samples. Otherwise, $\mathbf{x}_i$ is not selected).
However, it is more reasonable to suppose that a data point can be mainly recovered from its neighbors \cite{hu2013active,cai2012manifold}.
Intuitively, if the distance between the reconstructed point and the selected point is large, the contribution of the selected point should be small to the reconstruction of the target point, and thus the reconstruction coefficient should be penalized. In light of this point, we incorporate a regularization term into (\ref{obj4}) as:
\begin{align}\label{obj5}
\min\limits_{\mathbf{W}\in \mathbb{R}^{n\times d}} \ &\|\mathbf{X}-\mathbf{XWX}\|_F^2+\alpha\|\mathbf{W}\|_{2,1}+\beta\|\mathbf{W}^T\|_{2,1}\nonumber\\
&+\gamma \|\mathbf{W}\|_{\ast}+\eta \|\mathbf{T}\odot(\mathbf{WX})\|_1,
\end{align}
where $\eta \geq 0$ is a regularization parameter, and $\odot$ denotes the element-wise multiplication of two matrices. $\mathbf{T}$ is a weight matrix, where $\mathbf{T}_{ij}$ encodes the distance between the $i$-th and $j$-th samples. From the data reconstruction perspective, if two unit vectors have the same or opposite directions, their distance should be minimal, since either vector can be fully recovered by the other one; on the contrary, if the two vectors are orthogonal, their distance should be maximal, because they have little contribution to each other's reconstruction. Therefore, we use the absolute value of the cosine function of the angle between two feature vectors to measure their similarity, and define the inverse of the absolute value as their distance:
\begin{align}
\mathbf{T}_{ij}=\frac{1}{|\cos \theta_{ij}|},
\end{align}
where $\theta_{ij}$ denotes the angle between $\mathbf{x}_i$ and $\mathbf{x}_j$\footnote{When $\cos\theta_{ij}=0$, we can regularize $\mathbf{T}_{ij}$ as $\mathbf{T}_{ij}=\frac{1}{|\cos \theta_{ij}|+\varsigma}$, where $\varsigma$ is a very small positive constant.}.

After obtaining the optimal $\mathbf{W}$ in (\ref{obj5}), we can sort all the samples by the $l_2$ norm of the rows of $\mathbf{W}$ in descending order, and select the top $m$ samples as the representative ones. Similarly, we rank all the features by the $l_2$ norm of the columns of $\mathbf{W}$ in descending order, and choose the top $r$ features to represent the samples.

 We take the FG-NET dataset\footnote{The dataset is available at \url{http://sting.cycollege.ac.cy/alanitis/fgnetaging/index.htm}.} as an example to illustrate the effectiveness of the $l_{2,1}$ norm constraint on $\mathbf{W}$ and $\mathbf{W}^T$ in (\ref{obj5}). Figure \ref{visual_norm} (a) and (b) are the visualizations of $l_{2,1}$ norm of $\mathbf{W}$ and $\mathbf{W}^T$, respectively. Many rows and columns in $\mathbf{W}$ become sparse by adding the $l_{2,1}$ norm constraints on $\mathbf{W}$ and $\mathbf{W}^T$, which means that $\mathbf{W}$ can conduct sample selection and feature selection simultaneously.

\begin{figure}
\centering
\subfigure[$\|\mathbf{W}\|_{2,1}$]{\includegraphics[width=0.49\linewidth]{row_cropped.pdf}}
\subfigure[$\|\mathbf{W}^T\|_{2,1}$]{\includegraphics[width=0.47\linewidth]{column_cropped.pdf}}
\caption{The visualization of the learned $\mathbf{W}$ on the FG-NET dataset. (a) Each row is the $l_2$ norm value of each row of $\mathbf{W}$. (b) Each column is the $l_2$ norm value of each column of $\mathbf{W}$. Dark blue denotes that the values are close to zero.}
\label{visual_norm}
\end{figure}

\subsection{Optimization Algorithm}
Although the problem (\ref{obj5}) is convex, it is not easy to be solved by sub-gradient type methods since different structured non-smooth terms are involved.
In this section, we employ the alternating direction method of multipliers (ADMM) \cite{gabay1976dual} to solve (\ref{obj5}). Theoretical results will be given then including the global convergence and iteration complexity.

In order to solve (\ref{obj5}), we first introduce two variables $\mathbf{Z}$ and $\mathbf{W}_1$ to convert (\ref{obj5}) to the following equivalent objective:
\begin{align}\label{obj6}
\min\limits_{\mathbf{W},\tilde{\mathbf{W}},\mathbf{Z}} \ &\|\mathbf{X}-\mathbf{XWX}\|_F^2+\alpha\|\mathbf{W}\|_{2,1}+\beta\|\mathbf{W}^T\|_{2,1}\nonumber\\
&+\gamma \|\tilde{\mathbf{W}}\|_{\ast}+\eta \|\mathbf{T}\odot \mathbf{Z}\|_1 \nonumber\\
s.t. \ &\mathbf{WX}=\mathbf{Z}, \mathbf{W}=\tilde{\mathbf{W}}.
\end{align}
The augmented Lagrange function of (\ref{obj6}) is
\begin{align}\label{obj7}
&\qquad \mathcal{L}_{\rho_1,\rho_2}(\mathbf{W},\mathbf{Z},\tilde{\mathbf{W}},\Lambda_1,\Lambda_2):=\|\mathbf{X}-\mathbf{XWX}\|_F^2\nonumber\\
&+\alpha\|\mathbf{W}\|_{2,1}+\beta\|\mathbf{W}^T\|_{2,1}+\gamma \|\tilde{\mathbf{W}}\|_{\ast}+\eta \|\mathbf{T}\odot \mathbf{Z}\|_1 \nonumber\\
&+\langle\Lambda_1,\mathbf{WX}-\mathbf{Z}\rangle+\langle\Lambda_2,\mathbf{W}-\tilde{\mathbf{W}}\rangle +\frac{\rho_1}{2}\|\mathbf{WX}-\mathbf{Z}\|_F^2\nonumber\\
&+\frac{\rho_2}{2}\|\mathbf{W}-\tilde{\mathbf{W}}\|_F^2,
\end{align}
where $\Lambda_1$ and $\Lambda_2$ are Lagrange multipliers. $\rho_1$ and $\rho_2$ are the constraint violation penalty parameters.
From the augmented Lagrangian function, we can find that the subproblems about $Z$ and $\tilde{W}$ are totally separable, as a result we can introduce the classical two-block ADMM here, while considering $W$ and $(Z,\tilde{W})$ as two-block variables.
Next, we will introduce how to solve these subproblems in detail.
\begin{table}
\begin{center}
\label{tableMAEs}
\begin{tabular}{l}
\hline
\textbf{Algorithm 1} \  L-BFGS for the subproblem about $W$ \\
\hline
\textbf{Input:} Starting point $\mathbf{p}_0$, an integer $m>0$, and a \\
\ \ \ \ \ \ \ \ \ \ \ \ symmetric and positive definite matrix $\mathbf{H}_0$.\\
 \textbf{Initialize}: $k=0$.\\
\textbf{Repeat} \\
 \ \ \ \ \ \ 1. computing $d_k\leftarrow\mathbf{H}_k\nabla f_k$ using a two-loop recursion, \\
  \ \ \ \ \ \ \ \ \ \ where $\nabla f_k$ is the sub-gradient of $f(\mathbf{p})$ at $\mathbf{p}_k$; \\
 \ \ \ \ \ \ 2. computing $\mathbf{p}_{k+1}\leftarrow \mathbf{p}_k-\alpha_kd_k$, where $\alpha_k$ satisfies \\
 \ \ \ \ \ \ \ \ \ \ the Wolfe conditions;\\
 \ \ \ \ \ \ 3. $\mathbf{s}_k\leftarrow \mathbf{p}_{k+1}-\mathbf{p}_k$;\\
 \ \ \ \ \ \ 4. $\mathbf{y}_k\leftarrow\nabla f_{k+1}-\nabla f_k$;\\
 \ \ \ \ \ \ 5. $\widehat{m}\leftarrow \min \{k,m-1\}$; \\
 \ \ \ \ \ \ 6. updating Hessian matrix $\mathbf{H}_k$ using the pairs \\
 \ \ \ \ \ \ \ \ \ \ $\{\mathbf{y}_j,\mathbf{s}_j\}_{j=k-\widehat{m}}^k$;\\
 \ \ \ \ \ \ 7. $k\leftarrow k+1$;\\
\textbf{Until} Convergence criterion satisfied. \\
\textbf{Output:} $\mathbf{p}_k$.\\
\hline
\end{tabular}
\end{center}
\end{table}

Compute the subproblem about $\mathbf{W}$: When the other variables are fixed with the former iteration result $(Z^k, \tilde{W}^k,\Lambda_1^k,\Lambda_2^k)$, the subproblem about $W$ is as follows:
\begin{align}\label{subW}
&\mathbf{W}^{k+1}=\arg\min_{\mathbf{W}}\mathcal{L}_{\rho_1,\rho_2}(\mathbf{W},\mathbf{Z}^k,\tilde{\mathbf{W}}^k,\Lambda_1^k,\Lambda_2^k)\nonumber\\
&=\arg \min_{\mathbf{W}}\|\mathbf{X}-\mathbf{XWX}\|_F^2+\alpha\|\mathbf{W}\|_{2,1}+\beta\|\mathbf{W}^T\|_{2,1}\nonumber\\
& +\frac{\rho_1}{2}\|\mathbf{WX}-\mathbf{Z}^k+\frac{\Lambda_1^k}{\rho_1}\|_F^2+\frac{\rho_2}{2}\|\mathbf{W}-\tilde{\mathbf{W}}^k+\frac{\Lambda_2^k}{\rho_2}\|_F^2.
\end{align}

Since these is no closed-from solution of $\mathbf{W}$, so we adopt a gradient-based method to derive the optimal $\mathbf{W}$. Here we choose the limited-memory BFGS (L-BFGS) algorithm, due to its efficiency for large-scale optimization problems \cite{liu1989limited}, which is outlined in Algorithm 1.

Computing the subproblem about $\mathbf{Z}$: When fixing the other variables, we can update ${\mathbf{Z}}$ by
\begin{align}\label{subz}
{\mathbf{Z}}^{k+1}=\arg\min_{{\mathbf{Z}}}\mathcal{L}_{\rho_1,\rho_2}(\mathbf{W}^{k+1},\mathbf{Z},\tilde{\mathbf{W}}^{k},\Lambda_1^k,\Lambda_2^k)\nonumber\\
=\arg\min_{{\mathbf{Z}}} \eta \|\mathbf{T}\odot \mathbf{Z}\|_1+\frac{\rho_1}{2}\|{\mathbf{Z}}-\mathbf{W}^{k+1}\mathbf{X}-\frac{\Lambda_1^k}{\rho_1}\|_F^2.
\end{align}

The problem (\ref{subz}) can be solved by the following matrix shrinkage operation Lemma \cite{lin2009augmented}:

\newtheorem{thm}{Lemma}[section]
\begin{thm}\label{theo1}
For $\mu >0$, and $\mathbf{K}\in \mathbb{R}^{s\times t}$, the solution of the problem
\begin{align}
\min_{\mathbf{L}\in \mathbb{R}^{s\times t}}\mu\|\mathbf{L}\|_1+\frac{1}{2}\|\mathbf{L}-\mathbf{K}\|_F^2, \nonumber
\end{align}
is given by $\mathnormal{L}_\mu(\mathbf{K})\in\mathbb{R}^{s\times t}$, which is defined componentwisely by
\begin{align}\label{lmuk}
(\mathnormal{L}_\mu(\mathbf{K}))_{ij}:=\max\{|\mathbf{K}_{ij}|-\mu, 0\}\cdot sgn(\mathbf{K}_{ij}),
\end{align}
\end{thm}
where $sgn(t)$ is the signum function of $t\in \mathbf{R}$, i.e.,
\begin{align}
sgn(t):=
\left\{
\begin{array}{cc}
+1 & \text{if} \ t>0, \nonumber\\
0 & \text{if} \ t=0, \nonumber\\
-1 & \text{if}\  t<0.\nonumber
\end{array}
\right.
\end{align}

Based on Lemma \ref{theo1}, we can obtain a closed-form solution of $\mathbf{Z}$ whose ($i,j$)-th entry is expressed as
\begin{align}\label{optZ}
\mathbf{Z}_{ij}:=&\max\{|(\mathbf{W}^{k+1}\mathbf{X}+\frac{\Lambda_1^k}{\rho})_{ij}|-\frac{\eta\cdot\mathbf{T}_{ij}}{\rho_1},0\}\nonumber\\
&\cdot sgn((\mathbf{W}^{k+1}\mathbf{X}+\frac{\Lambda_1^k}{\rho_1})_{ij}).
\end{align}

Computing the subproblem about $\tilde{\mathbf{W}}$: When the other variables are fixed, $\tilde{\mathbf{W}}$ can be updated as
\begin{align}\label{subWhat}
\tilde{\mathbf{W}}^{k+1}=\arg\min_{\tilde{\mathbf{W}}}\mathcal{L}_{\rho_1,\rho_2}(\mathbf{W}^{k+1},\mathbf{Z}^{k+1},\tilde{\mathbf{W}},\Lambda_1^k,\Lambda_2^k)\nonumber\\
=\arg\min_{\tilde{\mathbf{W}}}\gamma \|\tilde{\mathbf{W}}\|_{\ast}+\frac{\rho_2}{2}\|\tilde{\mathbf{W}}-\mathbf{W}^{k+1}-\frac{\Lambda_2^k}{\rho_2}\|_F^2.
\end{align}

In order to solve the subproblem (\ref{subWhat}), we first introduce the following nuclear norm based shrinkage operation Lemma \cite{cai2010singular}:

\begin{thm}\label{theorom_nuclear_norm}
Let $\mathnormal{L}_\mu(\mathbf{K})$ be defined as in (\ref{lmuk}), $\mathbf{K}\in \mathbb{R}^{s\times t}$ whose rank is $l$, and $\mu>0$, the solution of the problem
 \begin{align}
 \min_{\mathbf{L}\in \mathbb{R}^{s\times t}}\mu \|\mathbf{L}\|_{\ast}+\frac{1}{2}\|\mathbf{L-K}\|^2_F, \nonumber
 \end{align}
 is given by $\mathcal{D}_\mu(\mathbf{K})\in \mathbb{R}^{s\times t}$, which is defined by
 \begin{align}
 \mathcal{D}_\mu(\mathbf{K}):=\mathbf{U}diag(\mathnormal{L}_\mu(\Sigma))\mathbf{V}^T,\nonumber
 \end{align}
 where $\mathbf{U}\in \mathbb{R}^{s\times l}$, $\mathbf{V}\in \mathbb{R}^{t\times l}$, and $\Sigma\in\mathbb{R}^{l\times l}$ by the singular value decomposition (SVD) of $\mathbf{K}$:
 \begin{align}
 \mathbf{K}=\mathbf{U}\Sigma \mathbf{V}^T \ \text{and} \ \Sigma=diag(\sigma_1,\sigma_2,\ldots,\sigma_l)\nonumber
 \end{align}
\end{thm}

Based on Lemma \ref{theorom_nuclear_norm}, we can obtain a closed form solution of (\ref{subWhat}).

The key steps of the proposed ALFS algorithm are summarized in Algorithm 2.
We can also extend our method to the kernel version by defining a new data representation to incorporate the kernel information as in \cite{zhang2013learning}.
\begin{table}[htb]
\begin{center}
\label{activefeaturelearning}
\begin{tabular}{l}
\hline
\textbf{Algorithm 2} \   The ALFS Algorithm \\
\hline
\textbf{Input:} The data matrix $\mathbf{X}\in\mathbb{R}^{d\times n}$, parameter $\alpha$, $\beta$, $\gamma$,\\
 \ \ \ \ \ \ \ \ \ \ \ \  and $\eta$.\\
 \textbf{Initialize}: $\mathbf{W}^0=\tilde{\mathbf{W}}^0=\textbf{0}$, $\mathbf{Z}^0=\textbf{0}$, $\Lambda_1^0=\textbf{0}$, $\Lambda_2^0=\textbf{0}$,\\
 $\rho_1=\rho_2=10^{-6}, \max_\rho=10^{10}$, $\tau=1.1$, $\epsilon=10^{-3}$, $k=0$.\\
\textbf{while} not converged \textbf{do} \\
 \ \ \ \ \ \ 1. fix the other variables and update $\mathbf{W}^{k+1}$ by \\
 \ \ \ \ \ \ \ \ \ Algorithm 1;\\
 \ \ \ \ \ \ 2. fix the other variables and update $\mathbf{Z}^{k+1}$ by (\ref{optZ});\\
 \ \ \ \ \ \ 3. fix the other variables and update $\tilde{\mathbf{W}}^{k+1}$ by\\
  \ \ \ \ \ \ \ \ \ \ $\tilde{\mathbf{W}}^{k+1}=\arg\min\limits_{\tilde{\mathbf{W}}}\gamma \|\tilde{\mathbf{W}}\|_{\ast}+\frac{\rho_2}{2}\|\tilde{\mathbf{W}}-\mathbf{W}^{k+1}-\frac{\Lambda_2^k}{\rho_2}\|_F^2;$\\
 \ \ \ \ \ \ 4. update the multipliers\\
  \ \ \ \ \ \ \ \ \ \ $\Lambda_1^{k+1}=\Lambda_1^{k}+\rho_1(\mathbf{W}^{k+1}\mathbf{X}-\mathbf{Z}^{k+1})$,\\
  \ \ \ \ \ \ \ \ \ \ $\Lambda_2^{k+1}=\Lambda_2^{k}+\rho_2(\mathbf{W}^{k+1}-\tilde{\mathbf{W}}^{k+1})$;\\
 \ \ \ \ \ \ 5. update the parameter $\rho_1$ and $\rho_2$ by \\
  \ \ \ \ \ \  \ \ \ \ \ $\rho_1 = \min(\tau\rho_1, \max_\rho)$,\\
   \ \ \ \ \ \  \ \ \ \ \ $\rho_2= \min(\tau\rho_2, \max_\rho)$;\\
  \ \ \ \ \ \ 6. $k\leftarrow k+1$;\\
  \ \ \ \ \ \ 7. check the convergence conditions\\
  \ \ \ \ \ \ \ \ \ \ $\|\mathbf{W}^k\mathbf{X}-\mathbf{Z}^k\|_\infty <\epsilon$ and $\|\mathbf{W}^k-\tilde{\mathbf{W}}^k\|_\infty<\epsilon$ and \\
  \ \ \ \ \ \ \ \ \ \ $|\frac{f(\mathbf{W}^k)-f(\mathbf{W}^{k-1})}{f(\mathbf{W}^{k-1})}|<\epsilon$, where $f(\mathbf{W}^k)$ is the \\
  \ \ \ \ \ \ \ \ \ \ objective function value of (\ref{obj5}) at the point $\mathbf{W}^k$. \\
 \textbf{end while}\\
 \textbf{Output:} The matrix $\mathbf{W}^k\in\mathbb{R}^{n\times d}$.\\
\hline
\end{tabular}
\end{center}
\end{table}

\subsection{Algorithm Analysis}
\medskip
{From the framework of ALFS, we can find that Algorithm 2 is the direct application of the classical two-block ADMM, although the problem has more than two block variables. All the subproblems in Algorithm 2 have closed-form solutions except $\mathbf{W}$, which is computed by the L-BFGS algorithm. Based on the classical convergence results, we can obtain the global convergence of {{Algorithm 2}} to the primal-dual optimal solution of problem (\ref{obj6}) (see \cite{boyd2011distributed,HeLiaoHanYang2002}). Further in \cite{HeYuan2012,HeYuan2014}, He $\&$ Yuan proves two kinds of iteration complexity results of ADMM, in ergodic and non-ergodic case. They present the global convergence rate by theoretically calculating the optimality condition gap after $k$ iterations. In the following we present both the global convergence and the iteration complexity results of Algorithm 2.

\begin{theorem}
For given constant parameters $\alpha$, $\beta$, $\gamma$, $\eta$ and given constant penalty parameters $\rho_1$, $\rho_2$. Denote the iteration sequence generated by {{Algorithm 2}} as
$$ {\mathbf{\Sigma}}^k := \left\{{\mathbf{W}}^k,{\mathbf{Z}}^k,{\mathbf{\tilde{W}}}^k,\Lambda_1^k,\Lambda_2^k  \right\},{\mathbf{\tilde{\Sigma}}}^k := \frac{1}{k+1} \sum_{t=0}^k {\mathbf{\Sigma}}^t,$$
$${\mathbf{\Sigma}}_1^k := \left\{{\mathbf{W}}^k,{\mathbf{Z}}^k,{\mathbf{\tilde{W}}}^k \right\}, {\mathbf{\Sigma}}_2^k := \left\{\Lambda_1^k,\Lambda_2^k  \right\}.$$
Then we have the following results:
\begin{enumerate}
\item (Global Convergence) The sequence $\left\{ {\mathbf{\Sigma}}^k \right\}$ converges to a primal-dual optimal solution pair $({\mathbf{W}}^{\infty}$,${\mathbf{Z}}^{\infty}$,${\mathbf{\tilde{W}}}^{\infty}$,$\Lambda_1^{\infty}$,$\Lambda_2^{\infty})$, where $({\mathbf{W}}^{\infty},{\mathbf{Z}}^{\infty},{\mathbf{\tilde{W}}}^{\infty})$ is the global optimal solution of problem (\ref{obj6})
 and ${\mathbf{W}}^{\infty}$ is the global optimal solution of problem (\ref{obj5}).
\item (Constraint Satisfactory) Both constraint violations will converge to zero, e.g.
$$
\left\| {\mathbf{W}}^k {\mathbf{X}} - {\mathbf{Z}}^k \right\|_F \rightarrow 0, \quad \left\| {\mathbf{\tilde{W}}}^k - {\mathbf{W}}^k \right\|_F \rightarrow 0.
$$
\item (Ergodic Iteration Complexity) Let $({\mathbf{W}}^*$,${\mathbf{Z}}^*$, ${\mathbf{\tilde{W}}}^*$,$\Lambda_1^*$,$\Lambda_2^*)$ be an optimal solution pair, we have
\begin{equation}\label{Ergodic_IC}
{\cal{L}}_{\rho_1,\rho_2} ({\mathbf{\tilde{\Sigma}}}_1^k, {\mathbf{\Sigma}}_2^*) - {\cal{L}}_{\rho_1,\rho_2} ({\mathbf{\Sigma}}_1^*, {\mathbf{\tilde{\Sigma}}}_2^k) \le \frac{ C_1 }{k+1},
\end{equation}
where $C_1$ denotes a constant related with ${\mathbf{\Sigma}}^0$ and ${\mathbf{\Sigma}}^*$.
\item (Non-ergodic Iteration Complexity) The non-ergodic iteration complexity can be written as
\begin{equation}\label{Nonergodic_IC}
\left\| {\mathbf{\Sigma}}^k - {\mathbf{\Sigma}}^{k+1} \right\|_{\cal{H}}^2 \le \frac{C_2}{k+1},
\end{equation}
where $C_2$ also denotes a constant related with ${\mathbf{\Sigma}}^0$ and ${\mathbf{\Sigma}}^*$ and ${\cal{H}}$ is a matrix related with ${\mathbf{X}}$ as follows,
\begin{equation}
{\cal{H}} = \left( \begin{array}{ccccc}
				\rho_1 {\mathbf{X}}^T {\mathbf{X}} + \rho_2 {\mathbf{I}} &{\mathbf{0}}&{\mathbf{0}}&{\mathbf{0}}&{\mathbf{0}} \\
				{\mathbf{0}} & \rho_1 {\mathbf{I}} & \ddots & \ddots&{\mathbf{0}}\\
				{\mathbf{0}} & \ddots & \rho_2 {\mathbf{I}} & \ddots&{\mathbf{0}}\\
				{\mathbf{0}} & \ddots & \ddots & \frac{1}{\rho_1} {\mathbf{I}}&{\mathbf{0}}\\
				{\mathbf{0}} & {\mathbf{0}} & {\mathbf{0}} & {\mathbf{0}} & \frac{1}{\rho_2}{\mathbf{I}}\\
				\end{array} \right).\nonumber
\end{equation}
\end{enumerate}
\end{theorem}

We do not present the detailed proof here, because this theorem is just the basic theoretical results in \cite{HeLiaoHanYang2002,HeYuan2012}. The first and second parts of this theorem show the global convergence of the presented algorithm, including sequence convergence and constraint convergence. From the first part, we can find that the sequence converges to the primal-dual optimal solution pair, while the second part shows the two linear constraints converge to zero in the sense of {\em{Frobenius}} norm.

The third and fourth parts above show a global convergence speed of ADMM, in the sense of ergodic and non-ergodic respectively. (\ref{Ergodic_IC}) denotes the ergodic iteration complexity, which denotes the characterization of $\epsilon$-optimal based on primal-dual optimality gap as follows,
\begin{eqnarray}
\hbox{Gap}({\mathbf{\Sigma}}_1,{\mathbf{\Sigma}}_2 ) \!\!\!\!&:=&\!\!\!\!  {\cal{L}}_{\rho_1,\rho_2} ({\mathbf{\Sigma}}_1, {\mathbf{\Sigma}}_2^*) - {\cal{L}}_{\rho_1,\rho_2} ({\mathbf{\Sigma}}_1^*, {\mathbf{\Sigma}}_2)\nonumber\\
&\le&\!\!\!\! \epsilon.
\end{eqnarray}
Thus, it means that after $k$ iterations, we can obtain an ${\cal{O}}(1/k)$-optimal solution. (\ref{Nonergodic_IC}) calculates the optimality condition between adjacent iterations, although this can not indicate convergence, but it really can accelerate the global convergence.

The above theorem not only shows the global convergence of {{Algorithm 2}}, but also presents two cases of iteration complexity. The global convergence means that the generated sequence converges to the optimal solution based on any initial point. Further the iteration complexity results mean that how good the iteration result is after $k$ iterations. We can also find that both iteration complexity results are $O(1/k)$, which is in the same order with many first-order algorithms.

\section{RELATED WORK}
As described, the work most related to our proposed approach is the second group active learning methods that intend to select the most representative samples.
In this section, we will briefly provide a review of the approaches in this group. Among them, the most popular one is the Transductive Experimental Design (TED) \cite{yu2006active}.  TED aimed to find a representative sample subset from the unlabeled dataset, such that the dataset can be best approximated by linear combinations of the selected samples.
Since this optimization problem is NP-hard, \cite{yu2006active} proposed a suboptimal sequential optimization algorithm and a non-greedy optimization algorithm to solve it, respectively.

Following TED, more active learning algorithms have been developed.
Cai and He \cite{cai2012manifold} extended TED to choose samples by utilizing a nearest neighbor graph to capture intrinsic local manifold structure, where the graph Laplacian is incorporated into a manifold adaptive kernel space.
Zhang et al. \cite{zhang2011active} adopted the idea from Locally Linear Embedding (LLE) \cite{roweis2000nonlinear} to find the reconstruction coefficients. They represented each sample by a linear combination of its neighbors, which can well preserve the local geometrical structure of the data.
Similar to \cite{zhang2011active}, Hu et al. \cite{hu2013active} incorporated the local geometrical information into the active learning process. Specifically, they introduced a regularization term to make the nearer neighbors have much effect on the linear reconstruction of data point, and penalized the selected samples distant from the reconstructed sample severely.
Nie et al. \cite{nie2013early} proposed a novel method to relax the objective of TED to an efficient convex formulation, and utilized the robust sparse representation loss function to reduce the effect of outliers.

\section{EXPERIMENT}
We evaluate the performance of our ALFS on six real-world datasets, including one speech signal processing area dataset LSVT Voice Rehabilitation, two preprocessed
microarray data sets from \cite{nie2010efficient}, i.e., Lung and Glioma, one face aging estimation dataset FG-NET (Five age groups are estimated in the experiment),  one video dataset Libras Movement, and one physical area dataset Musk. The LSVT Voice Rehabilitation dataset, the Libras Movement dataset, and the Musk dataset are downloaded from UCI Machine Learning Repository\footnote{\url{http://archive.ics.uci.edu/ml/datasets.html.}}. Datasets from different areas serve as
a good test bed for a comprehensive evaluation. Table \ref{datasets} summarizes the details of the datasets used in the experiments.
\begin{table}
\small
\begin{center}
\caption{Summary of experimental datasets. $\#$Feature, $\#$Sample, $\#$Train, $\#$Test, and $\#$Cat denote the number of features, the number of samples, the number of training samples, the number of testing samples, and the number of categories, respectively.}
\label{datasets}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
Dataset &$\#$Feature   & $\#$Sample & $\#$Train & $\#$Test  & $\#$ Cat \\
\hline
LSVT V. R. &309           & 126     & 50            & 76      & 2 \\
\hline
Musk      &168            & 476     &50             & 426     & 2 \\
\hline
Lung     & 3312             & 203   &50 & 153 & 5 \\
\hline
Glioma   & 4434           & 50     &  30  & 20  & 4 \\
\hline
FG-NET   & 907            & 1002   &100   & 902 & 5 \\
\hline
Libras Mov.& 90           & 360  &200 & 160 & 15 \\
\hline
\end{tabular}
\end{center}
\end{table}

Since ALFS is related to the second group active learning algorithms, we compare it with some classic approaches in this group to demonstrate the effectiveness of ALFS. The compared methods in the experiments are listed as follows:
\begin{itemize}
\item
Random Sampling (RS): randomly selects samples from the training dataset, which is used as the baseline for active learning.
\item
Transductive Experimental Design (TED) \cite{yu2006active}\footnote{A sequential solver can be downloaded from  {\url{http://www.dbs.ifi.lmu.de/~yu_k/ted/}}.}: an active learning method developing experimental design in a transductive setting.
\item
RRSS \cite{nie2013early}\footnote{The code can be downloaded from \url{http://www.escience.cn/people/fpnie/papers.html}.}: an active learning method taking advantage of robust representation and structure sparsity.
\item
Active Learning via Neighbor Reconstruction (ALNR) \cite{hu2013active}: an active learning method using neighborhood reconstruction.
\item
R-CUR \cite{mahoney2009cur}: a randomized algorithmic approach for solving CUR matrix factorization. We name it R-CUR for short.
\item
ALFS: our proposed method for selecting representative sample and feature selection simultaneously.
\end{itemize}
\begin{figure*}
\centering
\subfigure[Libras Movement]{\includegraphics[width=0.3\linewidth]{lib_query_cropped.pdf}}
\subfigure[age]{\includegraphics[width=0.3\linewidth]{age_query_cropped.pdf}}
\subfigure[Musk]{\includegraphics[width=0.3\linewidth]{musk_query_cropped.pdf}}
\subfigure[Glioma]{\includegraphics[width=0.3\linewidth]{glioma_query_cropped.pdf}}
\subfigure[LSVT Voice Rehabilitation]{\includegraphics[width=0.3\linewidth]{voice_query_cropped.pdf}}
\subfigure[Lung]{\includegraphics[width=0.3\linewidth]{lung_query_cropped.pdf}}
\caption{Comparison of different methods on six benchmark datasets. The curve shows the learning accuracy over queries.}
\label{query_accy}
\end{figure*}

To show the benefit of simultaneous active sample selection and feature selection, we also compare our ALFS against some feature selection approaches combined with the above active learning approaches, i.e., first using feature selection methods to reduce the dimensionality, and then applying the above active learning methods to select samples based on the new low-dimensional representation. We use two kinds of feature selection methods, i.e., $Q-\alpha$ \cite{wolf2005feature} and variance (Features corresponding to the maximum variance are selected to obtain the best expressive features), to combine with the active learning algorithms in the experiments, respectively.

In the experiments, for each dataset, we randomly divide the dataset into two parts: the training set and the testing set, which is shown in Table \ref{datasets}.
We apply the compared methods on the training set to select a certain number of samples for querying. After that, we learn the same decision tree classifier for all the methods based on these labeled samples, and evaluate the representativeness of the selected samples in terms of classification accuracy on the testing set.
We repeat every test case for 10 times, and report the average classification performance.

There are some parameters to be set in advance. The parameters $\alpha$, $\beta$, and $\eta$ in our algorithm  are searched from $\{0.1, 1, 10, 100\}$. The parameter $\lambda$ is always set to 1 (We found that when $\lambda=1$, the performance was consistently good on all the datasets).
For a fair comparison, the parameters in TED, RRSS, and ALNR are also searched from $\{0.1, 1, 10, 100\}$.
\begin{figure*}
\centering
\subfigure[Libras Movement]{\includegraphics[width=0.3\linewidth]{lib_q_cropped.pdf}}
\subfigure[age]{\includegraphics[width=0.3\linewidth]{age_q_cropped.pdf}}
\subfigure[Musk]{\includegraphics[width=0.3\linewidth]{musk_q_cropped.pdf}}
\subfigure[Glioma]{\includegraphics[width=0.3\linewidth]{glioma_q_cropped.pdf}}
\subfigure[LSVT Voice Rehabilitation]{\includegraphics[width=0.3\linewidth]{voice_q_cropped.pdf}}
\subfigure[Lung]{\includegraphics[width=0.3\linewidth]{lung_q_cropped.pdf}}
\caption{Comparison of Q + active learning algorithms on all the six datasets. Here, `Q' denotes the feature selection method $Q-\alpha$. The curve shows the learning accuracy over features.}
\label{feature_accy1}
\end{figure*}
\begin{figure*}
\centering
\subfigure[Libras Movement]{\includegraphics[width=0.3\linewidth]{lib_var_cropped.pdf}}
\subfigure[age]{\includegraphics[width=0.3\linewidth]{age_var_cropped.pdf}}
\subfigure[Musk]{\includegraphics[width=0.3\linewidth]{musk_var_cropped.pdf}}
\subfigure[Glioma]{\includegraphics[width=0.3\linewidth]{glioma_var_cropped.pdf}}
\subfigure[LSVT Voice Rehabilitation]{\includegraphics[width=0.3\linewidth]{voice_var_cropped.pdf}}
\subfigure[Lung]{\includegraphics[width=0.3\linewidth]{lung_var_cropped.pdf}}
\caption{Comparison of Var + active learning algorithms on all the six datasets. Here, `Var' denotes the feature selection method Variance. The curve shows the learning accuracy over features.}
\label{feature_accy2}
\end{figure*}

\subsection{Experimental Result}
\subsubsection{Comparison with Active Learning Algorithms}
In order to demonstrate the effectiveness of our ALFS in selecting representative samples, we compare ALFS with some state-of-the-art active learning algorithms. For ALFS and R-CUR, we vary the number of selected features from 10 to 100 with an incremental step of 10 on all the datasets except the Libras Movement dataset. Since the original feature dimension of the Libras Movement dataset is 90, we vary the number of selected features from 10 to 80 with an incremental step of 5\footnote{When the user inputs the desired number of samples $m$ and the number of features $r$, the final outputs $m'$ and $r'$ of R-CUR \cite{mahoney2009cur} may be slightly different $m$ and $r$, respectively. }.
The results are reported in Figure \ref{query_accy}. We can observe that our method achieves better performance than all the other candidates. Taking the Libras Movement dataset as an example, when the number of the selected samples is set to 150, ALFS obtains a classification result of $55.8\%$, attaining $10.7\%$ relative improvement over the second best result, i.e., ALNR. This result shows that feature selection is beneficial to select representative samples for active learning. In addition, we note that R-CUR is not better than  TED, RRSS and ALNR on almost all the datasets, and even worse on the FG-NET dataset and the LSVT Voice Rehabilitation dataset. The reason is that R-CUR \cite{mahoney2009cur} is a general CUR model and adopts a randomized algorithmic approach to seek the matrices $\mathbf{C}$ and $\mathbf{R}$ for satisfying (\ref{svd1}). It does not consider it as an optimization problem, making the selected samples and features hardly be the most representative, which limits R-CUR to be directly applied to active learning.

\subsubsection{Comparison with Feature Selection + Active Learning}
In order to demonstrate the necessary of simultaneous sample and feature selection, we compare ALFS with some feature selection methods combined with the active learning algorithms. We fix the number of the selected sample, and test the classification accuracies with different feature dimensions.
Figures \ref{feature_accy1} and \ref{feature_accy2} demonstrate the results. We can see that our method outperforms those approaches treating sample selection and feature selection as two separate steps.
Still taking the Libras Movement dataset as an example, when the number of selected features is set to 30, ALFS achieves $24.9\%$ relative improvement over $Q-\alpha$ combined with ALNR, and $24.2\%$ relative improvement over variance combined with ALNR. This indicates that simultaneous sample and feature selection is promising for obtaining good performance. In addition, we can observe that active learning combined with feature selection indeed improve the performance of only active learning under most of the cases.
\subsection{CPU Time and Sensitivity Analysis}
We test the CPU running time with different convergence tolerance $\epsilon$ on the FG-NET and Libras Movement datasets. The experiments are conducted on machines with Intel(R)-Core(TM) CPUs of 3.20 GHz and 4 GB RAM, and ALFS is implemented using MATLAB R2014b 64bit edition without parallel operation.
The result is shown in Figure \ref{time}. The CPU time grows linearly with $\epsilon$ increasing on the FG-NET dataset, while it is not sensitive to $\epsilon$ on the Libras Movement dataset.
%In addition, if we apply some parallel implementations on ADMM as in  or use more efficient programming language, the running time of ALFS can be further reduced.

We also study the sensitivity of parameters $\alpha$, $\beta$, $\gamma$, and $\eta$ in
our algorithm on the Libras Movement dataset. Figure \ref{parameter} shows
the results. With the fixed feature dimensions, our method is not sensitive to $\alpha$, $\beta$, $\gamma$, and $\eta$ with wide ranges.

\begin{figure}
\centering
\includegraphics[width=0.7\linewidth]{age_time_cropped.pdf}
\caption{CPU time vs. convergence tolerance $\epsilon$.}
\label{time}
\end{figure}

\begin{figure}
\centering
\subfigure[]{\includegraphics[width=0.48\linewidth]{alpha_cropped.pdf}}
\subfigure[]{\includegraphics[width=0.48\linewidth]{beta_cropped.pdf}}
\subfigure[]{\includegraphics[width=0.48\linewidth]{gamma_cropped.pdf}}
\subfigure[]{\includegraphics[width=0.48\linewidth]{eta_cropped.pdf}}
\caption{Sensitivity study of the parameters on the Libras Movement dataset.}
\label{parameter}
\end{figure}

\section{CONCLUSIONS AND FUTURE WORK}
In this paper, we present a unified framework to simultaneously conduct active sample learning and feature selection (ALFS). Given an unlabeled dataset, our formulation naturally and effectively incorporates feature and sample selection by solving a regularized optimization problem rooted from CUR factorization. We further relax the original NP-hard non-convex problem into a convex one by introducing the structured sparsity-inducing norms, which allows for efficient iterative optimization algorithm (ADMM). The superior performance of our method over the state-of-the-art methods is verified by extensive experimental evaluations with six benchmark datasets.

Several interesting directions can be followed up, which are not covered by our current work:
\begin{itemize}
\item
{\bf{Leveraging labeled samples}}: ALFS selects samples and features from a perspective of data reconstruction in an unsupervised setting. If label information is available, we can incorporate such prior information into our framework, e.g., taking the objective function of \cite{nie2008trace} as a regularization term. This would be helpful if a specific prediction task is actually only relevant to a few features and our `blind' feature selection method may keep unnecessary features although they are indispensable to represent the sample set itself.
\item
{\bf{Online learning}}: ALFS works in a batch mode, i.e., the unlabeled dataset is available. We can further extend our work to online learning mode, such that ALFS can efficiently and effectively handle the case when new samples are coming in.
\item
{\bf{Additional regularization terms}}:  In our work, motivated by the local reconstruction philosophy, we add the cross-sample regularization term as presented in Sec.2.3. This term alleviates the under-determination condition of the factorization problem, and contributes to the robustness of our method. Symmetrically, a cross-feature regularization term can be also applied.
\end{itemize}


%\begin{small}
\bibliographystyle{abbrv}
\bibliography{sig-alternate}  % sigproc.bib is the name of the Bibliography in this case
%\end{small}
%\appendix
%\textbf{A.\ \ PROOF OF THEOREM 3.1}\\
%PROOF.
%\appendix
%%Appendix A
%\section{PROOF OF THEOREM 3.1}
%\textsc{Proof}.
\end{document}

sig-alternate.bbl
\begin{thebibliography}{10}

\bibitem{bilgic2012combining}
M.~Bilgic.
\newblock Combining active learning and dynamic dimensionality reduction.
\newblock In {\em SIAM International Conference on Data Mining}, pages
  696--707, 2012.

\bibitem{boutsidis2014optimal}
C.~Boutsidis and D.~P. Woodruff.
\newblock Optimal cur matrix decompositions.
\newblock {\em arXiv preprint arXiv:1405.7910}, 2014.

\bibitem{boyd2011distributed}
S.~Boyd, N.~Parikh, E.~Chu, B.~Peleato, and J.~Eckstein.
\newblock Distributed optimization and statistical learning via the alternating
  direction method of multipliers.
\newblock {\em Foundations and Trends{\textregistered} in Machine Learning},
  3(1):1--122, 2011.

\bibitem{cai2012manifold}
D.~Cai and X.~He.
\newblock Manifold adaptive experimental design for text categorization.
\newblock {\em Knowledge and Data Engineering, IEEE Transactions on},
  24(4):707--719, 2012.

\bibitem{cai2010singular}
J.-F. Cai, E.~J. Cand{\`e}s, and Z.~Shen.
\newblock A singular value thresholding algorithm for matrix completion.
\newblock {\em SIAM Journal on Optimization}, 20(4):1956--1982, 2010.

\bibitem{Chattopadhyay2012}
R.~Chattopadhyay, Z.~Wang, W.~Fan, I.~Davidson, S.~Panchanathan, and J.~Ye.
\newblock Batch mode active sampling based on marginal probability distribution
  matching.
\newblock In {\em Proceedings of the 18th ACM SIGKDD International Conference
  on Knowledge Discovery and Data Mining}, pages 741--749. ACM, 2012.

\bibitem{cohn1996active}
D.~A. Cohn, Z.~Ghahramani, and M.~I. Jordan.
\newblock Active learning with statistical models.
\newblock {\em Journal of Artificial Intelligence Research}, 4:129--145, 1996.

\bibitem{fazel2002matrix}
M.~Fazel.
\newblock {\em Matrix rank minimization with applications}.
\newblock PhD thesis, PhD thesis, Stanford University, 2002.

\bibitem{freund1997selective}
Y.~Freund, H.~S. Seung, E.~Shamir, and N.~Tishby.
\newblock Selective sampling using the query by committee algorithm.
\newblock {\em Machine Learning}, 28(2-3):133--168, 1997.

\bibitem{gabay1976dual}
D.~Gabay and B.~Mercier.
\newblock A dual algorithm for the solution of nonlinear variational problems
  via finite element approximation.
\newblock {\em Computers \& Mathematics with Applications}, 2(1):17--40, 1976.

\bibitem{HeLiaoHanYang2002}
B.~He, L.-Z. Liao, D.~Han, and Y.~Hai.
\newblock A new inexact alternating directions method for monotone variational
  inequalities.
\newblock {\em Mathematical Programming}, 92(1):103--118, 2002.

\bibitem{HeYuan2012}
B.~He and X.~Yuan.
\newblock On the o(1/n) convergence rate of the douglas-rachford alternating
  direction method.
\newblock {\em SIAM Journal on Numerical Analysis}, 50(2):700--709, 2012.

\bibitem{HeYuan2014}
B.~He and X.~Yuan.
\newblock On non-ergodic convergence rate of douglas--rachford alternating
  direction method of multipliers.
\newblock {\em Numerische Mathematik}, pages 1--11, 2014.

\bibitem{he2011variance}
X.~He, M.~Ji, C.~Zhang, and H.~Bao.
\newblock A variance minimization criterion to feature selection using
  laplacian regularization.
\newblock {\em Pattern Analysis and Machine Intelligence, IEEE Transactions
  on}, 33(10):2013--2025, 2011.

\bibitem{hu2013active}
Y.~Hu, D.~Zhang, Z.~Jin, D.~Cai, and X.~He.
\newblock Active learning via neighborhood reconstruction.
\newblock In {\em Proceedings of the 23th International Joint Conference on
  Artificial Intelligence}, pages 1415--1421. AAAI Press, 2013.

\bibitem{huang2010active}
S.-J. Huang, R.~Jin, and Z.-H. Zhou.
\newblock Active learning by querying informative and representative examples.
\newblock In {\em Advances in neural information processing systems}, pages
  892--900, 2010.

\bibitem{kong2011dual}
X.~Kong, W.~Fan, and P.~S. Yu.
\newblock Dual active feature and sample selection for graph classification.
\newblock In {\em Proceedings of the 17th ACM SIGKDD International Conference
  on Knowledge Discovery and Data Mining}, pages 654--662. ACM, 2011.

\bibitem{lewis1994sequential}
D.~D. Lewis and W.~A. Gale.
\newblock A sequential algorithm for training text classifiers.
\newblock In {\em Proceedings of the 17th ACM SIGIR International Conference on
  Research and Development in Information Retrieval}, pages 3--12.
  Springer-Verlag New York, Inc., 1994.

\bibitem{li2012multi}
L.~Li, X.~Jin, S.~J. Pan, and J.-T. Sun.
\newblock Multi-domain active learning for text classification.
\newblock In {\em Proceedings of the 18th ACM SIGKDD International Conference
  on Knowledge Discovery and Data Mining}, pages 1086--1094. ACM, 2012.

\bibitem{lin2009augmented}
Z.~Lin, M.~Chen, L.~Wu, and Y.~Ma.
\newblock The augmented lagrange multiplier method for exact recovery of
  corrupted low-rank matrices.
\newblock {\em Technical report, UIUC Technical Report UILU-ENG-09-2215}, 2009.

\bibitem{liu1989limited}
D.~C. Liu and J.~Nocedal.
\newblock On the limited memory bfgs method for large scale optimization.
\newblock {\em Mathematical programming}, 45(1-3):503--528, 1989.

\bibitem{mahoney2009cur}
M.~W. Mahoney and P.~Drineas.
\newblock Cur matrix decompositions for improved data analysis.
\newblock {\em Proceedings of the National Academy of Sciences},
  106(3):697--702, 2009.

\bibitem{nie2010efficient}
F.~Nie, H.~Huang, X.~Cai, and C.~H. Ding.
\newblock Efficient and robust feature selection via joint $l_{2,1}$-norms
  minimization.
\newblock In {\em Advances in Neural Information Processing Systems}, pages
  1813--1821, 2010.

\bibitem{nie2013early}
F.~Nie, H.~Wang, H.~Huang, and C.~Ding.
\newblock Early active learning via robust representation and structured
  sparsity.
\newblock In {\em Proceedings of the 23th International Joint Conference on
  Artificial Intelligence}, pages 1572--1578. AAAI Press, 2013.

\bibitem{nie2008trace}
F.~Nie, S.~Xiang, Y.~Jia, C.~Zhang, and S.~Yan.
\newblock Trace ratio criterion for feature selection.
\newblock In {\em AAAI}, volume~2, pages 671--676, 2008.

\bibitem{raghavan2006active}
H.~Raghavan, O.~Madani, and R.~Jones.
\newblock Active learning with feedback on features and instances.
\newblock {\em The Journal of Machine Learning Research}, 7:1655--1686, 2006.

\bibitem{roweis2000nonlinear}
S.~T. Roweis and L.~K. Saul.
\newblock Nonlinear dimensionality reduction by locally linear embedding.
\newblock {\em Science}, 290(5500):2323--2326, 2000.

\bibitem{roy2001toward}
N.~Roy and A.~McCallum.
\newblock Toward optimal active learning through monte carlo estimation of
  error reduction.
\newblock In {\em Proceedings of International Conference on Machine Learning},
  pages 441--448, 2001.

\bibitem{wang2013querying}
Z.~Wang and J.~Ye.
\newblock Querying discriminative and representative samples for batch mode
  active learning.
\newblock In {\em Proceedings of the 19th ACM SIGKDD International Conference
  on Knowledge Discovery and Data Mining}, pages 158--166. ACM, 2013.

\bibitem{wolf2005feature}
L.~Wolf and A.~Shashua.
\newblock Feature selection for unsupervised and supervised inference: The
  emergence of sparsity in a weight-based approach.
\newblock {\em The Journal of Machine Learning Research}, 6:1855--1887, 2005.

\bibitem{yu2006active}
K.~Yu, J.~Bi, and V.~Tresp.
\newblock Active learning via transductive experimental design.
\newblock In {\em Proceedings of the 23th International Conference on Machine
  Learning}, pages 1081--1088. ACM, 2006.

\bibitem{zhang2011active}
L.~Zhang, C.~Chen, J.~Bu, D.~Cai, X.~He, and T.~S. Huang.
\newblock Active learning based on locally linear reconstruction.
\newblock {\em Pattern Analysis and Machine Intelligence, IEEE Transactions
  on}, 33(10):2026--2038, 2011.

\bibitem{zhang2013learning}
Y.~Zhang and D.-Y. Yeung.
\newblock Learning high-order task relationships in multi-task learning.
\newblock In {\em Proceedings of the 23-th International Joint Conference on
  Artificial Intelligence}, pages 1917--1923. AAAI Press, 2013.

\end{thebibliography}
