Optimal Algorithms for-subspace Signal Processing

Abstract—We describe ways to define and calculate-norm signal subspaces that are less sensitive to outlying data than-cal-culated subspaces. We start with the computation of the max-imum-projection principal component of a data matrix containing signal samples of dimension. We show that while the general problem is formally NP-hard in asymptotically large, , the case of engineering interest of fixed dimension and asymptoti-cally large sample size is not. In particular, for the case where the sample size is less than the fixed dimension, we present in explicit form an optimal algorithm of computational cost. For the case, we present an optimal algorithm of complexity. We generalize to multiple-max-projec-tion components and present an explicit optimal subspace cal-culation algorithm of complexity where is the desired number of principal components (subspace rank). We conclude with illustrations of-subspace signal processing in the fields of data dimensionality reduction, direction-of-arrival estima-tion, and image conditioning/restoration. Index Terms — norm, norm, dimensionality reduction, direction-of-arrival estimation, eigendecomposition, erroneous data, faulty measurements, machine learning, outlier resistance, subspace signal processing. I