Low-rank Matrix Approximation Using Point-wise Operators

The problem of extracting low dimensional structure from high dimensional data arises in many applications such as machine learning, statistical pattern recognition, wireless sensor networks, and data compression. If the data is restricted to a lower dimensional subspace, then simple algorithms using linear projections can find the subspace and consequently estimate its dimensionality. However, if the data lies on a low dimensional but nonlinear space (e.g., manifolds), then its structure may be highly nonlinear and hence linear methods are doomed to fail. In this paper we introduce a new technique for dimensionality reduction based on point-wise operators. More precisely, let An×n be a matrix of rank k ≪ n and assume that the matrix Bn×n is generated by taking the elements of A to some real power p. In this paper we show that based on the values of the data matrix B, one can estimate the value p and therefore, the underlying low-rank matrix A; i.e., we are reducing the dimensionality of B by using point-wise operators. Moreover, the estimation algorithm does not need to know the rank of A. We also provide bounds on the quality of the approximation and validate the stability of the proposed algorithm with simulations in noisy environments