| Processing high dimensional data arises in a number of real world applications such as financial data analysis, hyperspectral imagery, and video surveillance. The data are organized in a rectangular array with n rows and p columns, where the rows represent different measurements and the columns represent different features. High dimensional statistical inference studies signal detection and estimation problems in the scenario when n << p. The main challenge of high dimensional statistical inference is the curse of dimensionality phenomena. The curse of dimensionality leads to intractability of accurately approximating high-dimensional density function.;Nevertheless, data samples in many high dimensional problems come from an underlying low dimensional space or manifold. This limits the degrees of freedom (DOF) in the ambient space. This structure can be exploited for statistical inference. Another feature of high dimensional data is concentration of measure phenomena, which states that certain smooth random functions in high dimensional space are nearly constant. The philosophy is that under mild conditions it is easy to predict the behavior of high dimensional data.;In this thesis, we exploit the DOF structure in detection and estimation of high dimensional data together with concentration of measure inequalities to obtain new results. In particular we consider the sparsity model for compressed sensing, the joint sparse and Markov structure for blind deconvolution, the manifold model for outlier detection and the temporally local anomaly structure for time-series anomaly detection. We present a linear programming solution for signal support recovery from noisy measurements that leverages sparse constraint. We simultaneously reconstruct the unknown autoregressive filter and the driving process in light of the joint structure on sparsity and Markov property. We develop novel non-parametric adaptive anomaly detection algorithm for high dimensional data that can adapt to local sparse manifold structure. We develop a clustering algorithm that accounts for highly unbalanced proximal and complex shaped clusters based on the scheme of reweighting the graph edge similarity. We propose a new paradigm for time-series anomaly detection that exploits the local anomaly structure.;Our analysis in compressed sensing shows that the achievable bound in terms of SNR, the number of measurements, and admissible sparsity level of a linear programming solution matches the optimal information-theoretic in an order-wise sense. Our result in anomaly detection suggests that estimating high dimensional level-set can be avoided by computing a sufficient p-value statistic. The resulting anomaly detector is asymptotically uniformly most powerful against any uniformly mixing density. We also provide a generalization of this p-value statistic in time-series anomaly detection with false alarm control. |
