2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Are you suggesting that $X$ is a matrix but not necessarily a square matrix? $\endgroup$
    – hardmath
    Jun 26, 2015 at 1:37
  • 1
    $\begingroup$ 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! $\endgroup$
    – Ris
    Jun 26, 2015 at 15:41

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – Ris
    Jun 26, 2015 at 15:36
  • $\begingroup$ 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. $\endgroup$ Jun 26, 2015 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.