Thresholding for relaxed linear constraint to satisfy the combinatorial constraint

Question

I have to satisfy a combinatorial constraint in $y$ with $y_i \in \{0,1\}$ and $i = \{1,2,..,n\}$,

$\sum_i y_i \leq k$.

The process of obtaining y is as follows

1. Sample $x \in [0,1]^n$
2. Project x onto half space $\sum_i x_i \leq c_1$. (based on $L_1$ norm)
3. Threshold, $y_i = 1$, if $x_i \geq c_2$

Both $c_1$ and $c_2$ can be controlled. What should I choose $c_1$ and $c_2$ as?

I started with the simplest choice of $c_1$ as k and considered the case when n is quite large, and I get $c_2$ as k/(k+1) when k is divided into k+1 bins is the largest value that does not satisfy constraint. Is it correct? any mathematical way of showing it?

Edit : corrected hyperplane to halfspace in 2.

Answer 1

This depends on what you're doing - you could satisfy your constraint by just taking $y=0$ identically. If you're doing sparse regression, $c_2$ should be the $k$th-largest value for $x_i$.

I don't think there's a way to choose $c_1$ and $c_2$ independently of $x$ which makes your method work for all $x$. Note that $\sum_i x_i\le c_1$ isn't a hyperplane - it's a half-space (it's isomorphic to $x_1 \le 0$ instead of $x_1=0$). If we let $u \in [0,1]^n$ denote the closest point to $x$ in the half-space $\sum_i u_i\le c_1$, we subtract the same amount from each $x_i$ greater than $c_1/n$, stopping when we reach $c_1/n$. Thus, if $c_1 > k$, and all the $x_i$ are between $k/n$ and $c_1/n$, projecting onto the half-space will mean all the $u_i$ are equal, and we can't recover the $k$ best $u_i$. On the other hand, if $c_1 \le k$ and $c_2$ is fixed, then we might have all the $x_i$ less than $c_2$ if $c_2$ is fixed, so they are all set to 0, which is clearly not optimal.

(Of course, this depends what you're doing with the $x_i$. If you're doing sparse regression, use $c_2$ equal to the $k$th-largest $x_i$, otherwise we need more details).