2011 , Volume 16, № 2, p.3-11

Principal component analysis (PCA) is one of the most widely used methods for reducing the data size. In practice, data is known with uncertainty, so we need to apply PCA to this uncertain data. Several authors developed algorithms for PCA under interval uncertainty. It is known that in general, the problem of PCA under interval uncertainty is NP-hard. The usual NP-hardness proof uses situations in which all measurement results come with interval uncertainty. In practice, often, most measurements are reasonably accurate, and only a few (or even one) variables are measured with significant uncertainty. When we consider such situations, will the PCA still be NP-hard? In this paper, we prove that even in the simplest case when for each object, at most one data points comes with interval uncertainty, the PCA problem is still NP-hard.