Let $\mathbf{x}\in \mathbb{R}^n$, and let $\|\mathbf{x}\|_L$ be the sum of the $L$ largest absolute components of $\mathbf{x}$. That is to say, write the (absolute values of) components of $\mathbf{x}$ in descending order and sum the first $L$ components. This gives you the norm in question.

Now how is this norm equivalent to the following linear program? \begin{equation*} \begin{aligned} & \underset{\boldsymbol{\eta}}{\text{maximize}} && \Sigma_{i=1}^{n}|x_i|\,\eta_i \\ & \text{subject to} && \boldsymbol{\eta}^T\mathbf{1}=L\\ &&& \mathbf{0}\leq\boldsymbol{\eta}\leq \mathbf{1} \end{aligned} \end{equation*}

I guess it should be sufficient to show that the objective function with the given constraints is equivalent to the given norm?

  • $\begingroup$ wow. OK. My bad. I'll make the edit. $\endgroup$ – Abdullah Nazir Oct 8 '19 at 10:12
  • $\begingroup$ It pays off to push $\eta$s as much as possible to the highest $|x_i|$s. $\endgroup$ – Michal Adamaszek Oct 8 '19 at 10:37
  • $\begingroup$ Right. And hence, maximize. $\endgroup$ – Abdullah Nazir Oct 8 '19 at 10:40
  • $\begingroup$ I think the case in which components of \eta take on integer values (0 or 1) should be easy to show. Not sure about the case in which they vary continuously between zero and one. $\endgroup$ – Abdullah Nazir Oct 8 '19 at 10:46
  • $\begingroup$ There exists an optimal solution where $\eta$s are all $0$ or $1$. Because why would you take a fractional $\eta_i$ of a smaller $x_i$ where instead you can move that mass to the bigger $x_i$'s and increase the objective. $\endgroup$ – Michal Adamaszek Oct 8 '19 at 10:58

(Courtesy: Comment by Michal Adamaszek)

First, ignore the equality constraint and assume that the $\boldsymbol{\eta}$ is subject to inequality constraints only i.e. its components can only take on values between $0$ and $1$. So, how to maximize the objective function which is affine in $\boldsymbol{\eta}$ and has non-negative weights $|x_i|$? Clearly, $\boldsymbol{\eta}=\mathbf{1}$ will be optimal in this case. Now, also enforce the equality constraint i.e. at most $L$ of the components of $\boldsymbol{\eta}$ can take on the value $1$. Now which components would these be? To maximize the objective, these will precisely be the ones corresponding to the $L$ largest components of $|\mathbf{x}|$. Thus, the optimal value returned by this LP is same as the norm $||\mathbf{x}||_L$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.