On box-constrained total least squares problem

We study box-constrained total least squares problem (BTLS), which minimizes the ratio of two quadratic functions with lower and upper bounded constraints. We first prove that (BTLS) is NP-hard. Then we show that for fixed number of dimension, it is polynomially solvable. When the constraint box is centered at zero, a relative 4/7-approximate solution can be obtained in polynomial time based on SDP relaxation. For zero-centered and unit-box case, we show that the direct nontrivial least square relaxation could provide an absolute (n + 1)/2-approximate solution. In the general case, we propose an enhanced SDP relaxation for (BTLS). Numerical results demon-strate significant improvements of the new relaxation.