  We study several variants of decomposing a symmetric matrix into a sum of a
low-rank positive semidefinite matrix and a diagonal matrix. Such
decompositions have applications in factor analysis and they have been studied
for many decades. On the one hand, we prove that when the rank of the positive
semidefinite matrix in the decomposition is bounded above by an absolute
constant, the problem can be solved in polynomial time. On the other hand, we
prove that, in general, these problems as well as their certain approximation
versions are all NP-hard. Finally, we prove that many of these low-rank
decomposition problems are complete in the first-order theory of the reals;
i.e., given any system of polynomial equations, we can write down a low-rank
decomposition problem in polynomial time so that the original system has a
solution iff our corresponding decomposition problem has a feasible solution of
certain (lowest) rank.
