Provably Identifying Linear Constraints under Unknown and Singular Measurement Noise

Many scientific and engineering systems satisfy unknown linear relations, but only noisy measurements of their variables are available. Four issues make these relations challenging. Noise variances can differ across variables, measurement errors can be correlated, and the noise covariance matrix can be singular. Moreover, both the noise covariance matrix and the number of relations may be unknown. We address all four challenges by proposing a novel generalized eigenvalue decomposition (GenEVD) based algorithm that avoids inverting the noise covariance matrix unlike existing methods. Iterative PCA and ordinary least squares arise as special cases of our method. Our first algorithm alternates this spectral update with an identifiable supported-moment estimator of the noise covariance. Our second algorithm estimates the number of relations through a descending unity-eigenvalue test. We establish high-probability recovery of the constraint subspace, noise covariance matrix, and number of relations. We also prove local geometric convergence and obtain a subspace rate with minimax-optimal dependence on sample size and dimension. Controlled synthetic experiments and empirical study on seven real-world datasets validate the corresponding theoretical claims.