I need help on the below integer programming problem. \begin{equation} \displaystyle \min_{X} \| A - X^TX \|_F \\ \text{s.t}~ X\in \{-1,1\}^{n\times d} \end{equation} where $A \in \mathbb{R}^{d\times d} $ is given and $\|\|_F$ is the Frobenius norm.
I've seen people do coordinate descent by minimizing a column at a time for $X$, and reducing it to Binary Quadratic Programming. I'm generally unaware of integer programming; any suggestions on particular methods, references and how to approach the problem?
Thanks
First remark (kind of obvious): minimize the square Frobenius norm, it is equivalent and polynomial.
Second remark (which I guess you saw): your system is actually fourth-order, but can be turned into something quadratic (like any polynomial system) by adding variables and equations of the kind $x^2_i=y_j$
Once you have quadratic integer programming. If you are lucky and it is Semi-Definite Positive (which does not look like it here): solve it with SDP branch-and-bound
If you are not lucky, it is non-convex integer programming. Happily, you can linearize your system. I suggest Mr Glover's or McCormick's techniques, which are the "basis" for this (http://leeds-faculty.colorado.edu/glover/fred%20pubs/69%20-%20Improved%20Linear%20Integer%20Programming%20Formulations%20of%20Nonlinear%20Integer%20Problems%20_%20%20Fred%20Glover.pdf ; https://optimization.mccormick.northwestern.edu/index.php/McCormick_envelopes) or more recent works (http://www.sciencedirect.com/science/article/pii/S0166218X08000504 )
Once this is done, you can solve your system by a classic branch and bound algorithm.
Note : it would be a lot simpler if you could characterize all possible terms $X^TX$ as a function of $n$. Out of curiosity, did you?