A toy mixed-norm regression problem

Let \(f_k(x)\) be the sum of the \(k\) largest entries of \(|x|\).

It turns out that this function is a norm! Special cases:

• \(f_1(x) = \|x\|_{\infty}\)

• \(f_n(x) = \|x\|_1\).

Consider the minimum-norm regression problem:

\(\qquad \operatorname{minimize} ~f_k(x) + \gamma f_n(x) ~\text{ s.t. }~ A x = y\).

For a wide \(m \times n\) matrix \(A\), an \(m\)-vector \(y\), and a tuning parameter \(\gamma\).

The larger values of \(x\) are “more penalized” as \(\gamma\) gets smaller.

import cvxpy as cp
import itertools

def sum_abs_largest(expr, k):
    # implement me!
    return None

import numpy as np
import scipy.linalg as la
import scipy.sparse as sp
import time

def make_problem_data(n, m, true_k):
    np.random.seed(1)
    x_ref = np.zeros(n)
    idxs = np.random.choice(np.arange(n), true_k, replace=False)
    x_ref[idxs] = 10 + 100*np.random.rand(true_k)
    A = np.random.randn(m, n)
    v = np.random.normal(0, 1.0, m)
    v /= (m*la.norm(v))
    y = A @ x_ref + v
    return A, x_ref, y

def make_and_solve(loss, x):
    prob = cp.Problem(cp.Minimize(loss), [A @ x == y])
    tic = time.time()
    prob.solve(solver='ECOS')
    toc = time.time()
    t = toc - tic
    x_est = x.value
    return prob, x_est, t

n, m, true_k = 14, 7, 4
A, x_ref, y = make_problem_data(n, m, true_k)
x = cp.Variable(n)
gamma = cp.Parameter(pos=True)
gamma.value = 1e-3
k = 3

loss1 = sum_abs_largest(x, k) + gamma * cp.norm(x, 1)
prob1, x1, t1 = make_and_solve(loss1, x)
print(f'Solve time (home brewed)\n\t{t1}')

loss2 = cp.sum_largest(cp.abs(x), k) + gamma * cp.norm(x, 1)
prob2, x2, t2 = make_and_solve(loss2, x)
print(f'Solve time (cvxpy atom)\n\t{t2}')

disc = la.norm(x1 - x2) / min(la.norm(x1), la.norm(x2))
print(f'Discrepency between two solutions\n\t{disc}')

import matplotlib.pyplot as plt
%matplotlib inline

A1 = prob1.get_problem_data(solver='SCS')[0]['A']
plt.spy(A1, aspect='auto')
plt.show()

A2 = prob2.get_problem_data(solver='SCS')[0]['A']
plt.spy(A2, aspect='auto')
plt.show()