Jakub Marecek
Iterative Methods for Integer Least Squares

School of Mathematics
The University of Edinburgh
James Clerk Maxwell Building
The King's Buildings
Edinburgh EH9 3JZ
jakub.marecek@ed.ac.uk
Danny Kershaw

Least squares rank among the most fundamental problems in Scientific Computing, Signal Processing, and Statistics. Over the years, numerous variants of the problem have been studied. A variant, which has attracted much attention in recent years, is:

BOX-CONSTRAINED INTEGER LEAST SQUARES (BILS): Given integers $m, n > 0$ , a subset of integers $Q$ , matrix $H \in \ensuremath{\mathbbm{R}}^{m \times n}$ , and $y \in \ensuremath{\mathbbm{R}}^m$ , return $x\in Q^n$ minimising $\left\Vert {y - Hx} \right\Vert^2$ .

The solving BILS to optimality is hard, in a number of precise senses. Notably, it is NP-hard to approximate within any constant factor [#!MR1462727!#]. We present an iterative solver for the problem, based on novel convex programming relaxations. Such relaxations strengthen the least squares relaxation, obtained by omitting the integrality constraints. In each iteration, a small number of violated valid inequalities are added, and the relaxation is reoptimised.

There have been proposed numerous convex programming relaxations of BILS. (See Table  in the Appendix.) They seem to be, however, either too expensive to compute (e.g. high-dimensional semidefinite programming), or too weak (e.g. linear programming). We propose a hierarchy of progressively stronger relaxations in second order-cone programming (SOCP):

$$\min c^T x$$ (1)

$${\mathrm{s. t.}}\left\Vert A_i x + b_i \right\Vert _2 \leq c_i^T x + d_i, \quad i = 1,\dots,m$$

$$Ax = b,$$

Notice that solving a SOCP is only moderately more expensive than solving a linear program, but allows one to express the least-squares objective.

Our relaxations are based on the reformulation attributed to Atamtürk:

$$\min_{x \in Q^n} \left\Vert {y - Hx} \right\Vert$$ (2)

$$= \min_{x \in Q^n} x^T H^T H x - 2 y^T H x + y^T y$$ (3)

$$= \min_{x \in Q^n, t \in \ensuremath{\mathbbm{R}}^n} t^T t {\mathrm{s. t.}}Hx - y \le t, y - Hx \le t$$ (4)

$$= \min_{x \in Q^n, t_0 \in \ensuremath{\mathbbm{R}}, t \in \ensuremath{\mathbbm{R}}^n} t_0 {\mathrm{s. t.}}\vert y - Hx\vert \le t, t^T t \le t_0.$$ (5)

By removing the constraint $x\in Q^n$ in the original problem (), we would obtain the usual least squares relaxation. By removing the same constraint in the reformulated problem (), we obtain the single-cone SOCP relaxation:

$$z_r = \min_{x \in R^n, t_0 \in \ensuremath{\mathbbm{R}}, t \in \e... ...th{\mathbbm{R}}^n } t_0 {\mathrm{s. t.}}\vert Hx - y\vert \le t, t^T t \le t_0.$$ (6)

This relaxation () can be strengthened by the addition of violated valid inequalities (``cuts''), including variants of Chvátal-Gomory cuts [#!Cezik2005!#] and mixed-integer rounding (MIR) cuts [#!Atamturk2007!#].

Let us define the Conic Mixed Integer Rounding (MIR) function. For $0 \le f \le 1$ , the conic rounding function $\phi_f : \ensuremath{\mathbbm{R}}\to \ensuremath{\mathbbm{R}}$ is:

$$\phi_f(a) = \begin{cases}(1 - 2f)n - (a - n) & \text{if $n \le a ... ...,} \\ (1 - 2f)n + (a - n) - 2f &\text{if $n + f \le a \le n + 1$.} \end{cases}$$

The extension to vectors is element-wise. For pure integer programs () and $\alpha \ne 1$ , the conic rounding cut hence is:

$$\sum_{j = 1}^{n} \phi_{f_{\alpha}}(a_j / \alpha) - \phi_{f_{\alpha}}(b / \alpha) \le t / \vert\alpha\vert.$$

It is easy to see that for $\alpha \ne 1$ and $f_{\alpha} = b/\alpha - \left\lfloor {b / \alpha} \right\rfloor$ , conic rounding cuts are valid for pure integer programs (). With each cut added, we obtain a new relaxation.

The choice of a cut has to take into account its violation and numerical safety [#!Cook2009!#]. After adding at most three cuts in a row, the newly obtain relaxation is optimised, possibly using the previous solution. The optimisation of the second-order cone program is, again, performed using an iterative method, such as the primal-dual interior point method. The complexity of each iteration of the interior point method is dominated the complexity of a matrix inversion of a $(m+c) \times (n+ m + 1)$ matrix, where $n,m$ are the dimensions of the original matrix $H$ , and $c$ is the number of cuts added. The appendix details promising computational performance of this approach.

This approach lead to the development of low-power application specific integrated circuits for the problem, which is of great importance in mobile communications. There are systolic digital designs for much of the interior point method already available. This could be seen as an extension of Boyd's notion of real-time convex programming to real-time integer convex programming.