I am working on implementing mechanism 1 from this paper. I have limited knowledge on convex optimization and am not sure how to derive an explicit expression for the linear transformation of the unit ball.
Specifically, I have a set $\mathcal{C} = \{\theta \in \mathbb{R}^d : \lVert \theta \rVert_1 \leq 1\}$. I am wondering how to derive an expression for $\Phi \mathcal{C} = \{ \nu = \Phi \theta : \theta \in \mathcal{C} \}$, where $\Phi \in \mathbb{R}^{m \times d}$ is a known matrix with $m < d$. Explicitly deriving an expression for the convex set of $\Phi \mathcal{C}$ will allow me to use convex optimization over $\nu$.
Although I'm not sure how to approach this, there are a few things which are making this difficult for me:
- The constraint $\lVert \theta \rVert_1 \leq 1$ is difficult to efficiently implement with a matrix, since this matrix would need to have $2^d$ rows. There are ways to make this more efficient, but I'm not sure whether this is a good approach.
- I'm not sure how to derive an expression for the linear transformation of a convex set.
Another approach which would be equally useful is determining how to project a given $\nu$ back into $\Phi \mathcal{C}$, since the paper calls for me to use projected optimization. The only way I know how to do projection requires me to have an explicit expression for the convex set, which I am not sure how to calculate.
Any help would be appreciated!