# Solve $AX = B$ where $X^T X = C$

Is there a natural way to find the solution to

$$AX = B, X^TX = C \enspace \text{?}$$

$X$ is a matrix and has a small number of rows, and $A$ is sparse.

An approximate solution would be fine.

• Are you suggesting that $X$ is a matrix but not necessarily a square matrix?
– hardmath
Jun 26, 2015 at 1:37
• Ah yeah, I should have said "$X$ has fewer rows than columns". We're expecting $X$ to have maybe 10 rows and 50 columns. Thanks for the clarification!
– Ris
Jun 26, 2015 at 15:41

Your problem is related to low rank approximation problems, about which there has been a lot of research in recent years.

Are you looking for a solution in which $X$ has a specified number of rows, or are you trying to find the smallest number of rows possible?

In most cases, users are interested in finding $X$ such that $X^{T}X$ is close to $C$ (in e.g. the Frobenius norm.) Are you sure that you need to have $X^{T}X$ equal to $C$ to some fairly tight tolerance, or would you be willing to accept a solution with $\| X^{T}X-C \|_{F}$ reasonably small? Could you trade off that objective against the rank of $X$?

The occurrence of linear constraints on the elements of $X$ rather than on the elements of $X^{T}X$ is also unusual. Is it possible to write your constraints in terms of $X^{T}X$ rather than $X$?

In general, these low rank optimization problems are non-convex and NP-Hard. However, heuristic approaches using surrogate objective functions and semidefinite programming can be very effective in finding solutions with relatively low rank. Another alternative is to apply a more general nonlinear optimization method with $X$ as the variable (but the problems are non-convex so a local optimum might not be globally optimal.) See for example the SDPLR method of Burer and Monteiro.

• Thanks! Specified number of rows k vs smallest number of rows: Either would be fine; given the former we would be fine running an algorithm for each k = 1,2,... Finding something close to C in Frobenius norm would also be totally fine. I think the linear constraints will eventually be needed, but we were stuck even without them so progress without the linear constraints would still be helpful :). I will look into your suggestions!
– Ris
Jun 26, 2015 at 15:36
• Given that you know $k$ in advance, you'll likely be more interested in the SDPLR approach- I'd encourage you to take a look at that paper. Jun 26, 2015 at 15:53