2011 г., Том 16, № 2, с.3-11

Метод главных компонент (PCA) является одним из наиболее используемых методов для сокращения объема данных. На практике данные редко заданы точно, обычно - с неопределенностью, поэтому необходимо применять PCA. Известно, что в общем случае PCA при интервальной неопределенности - NP-сложная задача. Традиционное доказательство NP-сложности использует ситуации, в которых все результаты измерений известны с интервальной неопределенностью. На практике многие измерения,как правило, являются достаточно точными и лишь небольшая их часть имеет существенную неопределенность. Если ограничиться такими ситуациями, будет ли задача PCA NP-сложной? В статье показано, что даже в простейшем случае, когда объект имеет не более одной переменной с интервальной неопределенностью, задача PCA по-прежнему NP-сложной.