  This paper considers a quadratically-constrained cardinality minimization
problem with applications to digital filter design, subset selection for linear
regression, and portfolio selection. Two relaxations are investigated: the
continuous relaxation of a mixed integer formulation, and an optimized diagonal
relaxation that exploits a simple special case of the problem. For the
continuous relaxation, an absolute upper bound on the optimal cost is derived,
suggesting that the continuous relaxation tends to be a relatively poor
approximation. In computational experiments, diagonal relaxations often provide
stronger bounds than continuous relaxations and can greatly reduce the
complexity of a branch-and-bound solution, even in instances that are not
particularly close to diagonal. Similar gains are observed with respect to the
mixed integer programming solver CPLEX. Motivated by these results, the
approximation properties of the diagonal relaxation are analyzed. In
particular, bounds on the approximation ratio are established in terms of the
eigenvalues of the matrix defining the quadratic constraint, and also in the
diagonally dominant and nearly coordinate-aligned cases.
