Article Contents
Article Contents

On box-constrained total least squares problem

• * Corresponding author: Y. Xia

This research was supported by NSFC grants 11822103, 11571029, 11771056 and Beijing Natural Science Foundation Z180005

• 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 demonstrate significant improvements of the new relaxation.

Mathematics Subject Classification: Primary: 90C20, 90C32; Secondary: 65F20.

 Citation:

• Table 1.  Numerical comparison of lower bounds

 $(m,n)$ $l=0,u=50$ $l=0,u=100$ $l=0,u=255$ $v$(SDP) $v$(ISDP) $v$(SDP) $v$(ISDP) $v$(SDP) $v$(ISDP) (15, 10) 0.1847 0.1884 0.1742 0.1760 0.1675 0.1683 (50, 25) 0.4530 0.5043 0.4137 0.4425 0.3893 0.4011 (75, 50) 0.4732 0.5302 0.4214 0.4546 0.3893 0.4033 (100, 75) 0.3218 0.3825 0.2501 0.2875 0.2057 0.2229 (125,100) 0.4034 0.4805 0.3010 0.3541 0.2372 0.2646 (150,125) 0.3664 0.4496 0.2403 0.3028 0.1622 0.2163

Table 2.  Numerical comparison of CPU time

 $(m,n)$ $l=0,u=50$ $l=0,u=100$ $l=0,u=255$ $t$(SDP) $t$(ISDP) $t$(SDP) $t$(ISDP) $t$(SDP) $t$(ISDP) (15, 10) 0.69 2.70 0.34 1.35 0.41 1.41 (50, 25) 0.94 8.34 0.40 4.36 0.42 4.67 (75, 50) 1.44 36.81 0.70 19.16 0.68 20.76 (100, 75) 2.33 109.05 1.27 66.26 1.26 70.89 (125,100) 4.92 259.68 2.91 176.77 2.87 239.28 (150,125) 9.99 686.35 6.65 564.68 6.11 647.24

Tables(2)