  Dimensionality reduction is a classical technique widely used for data
analysis. One foundational instantiation is Principal Component Analysis (PCA),
which minimizes the average reconstruction error. In this paper, we introduce
the "multi-criteria dimensionality reduction" problem where we are given
multiple objectives that need to be optimized simultaneously. As an
application, our model captures several fairness criteria for dimensionality
reduction such as our novel Fair-PCA problem and the Nash Social Welfare (NSW)
problem. In Fair-PCA, the input data is divided into $k$ groups, and the goal
is to find a single $d$-dimensional representation for all groups for which the
minimum variance of any one group is maximized. In NSW, the goal is to maximize
the product of the individual variances of the groups achieved by the common
low-dimensional space.
  Our main result is an exact polynomial-time algorithm for the two-criterion
dimensionality reduction problem when the two criteria are increasing concave
functions. As an application of this result, we obtain a polynomial time
algorithm for Fair-PCA for $k=2$ groups and a polynomial time algorithm for NSW
objective for $k=2$ groups. We also give approximation algorithms for $k>2$.
Our technical contribution in the above results is to prove new low-rank
properties of extreme point solutions to semi-definite programs. We conclude
with experiments indicating the effectiveness of algorithms based on extreme
point solutions of semi-definite programs on several real-world data sets.
