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 the Fair-PCA problem introduced by Samadi, et. al. 2018 and
the Nash Social Welfare (NSW) problem. In the Fair-PCA problem, 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 maximum reconstruction error of any
one group is minimized. In NSW the goal is to maximize the product of the
individual variances of the groups achieved by the common low-dimensinal 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, resolving an open problem of Samadi,
et. al. 2018, 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 datasets.