Answer Happy

Consider a compressive sensing problem. x E R" is an unknown signal, which is known to be very sparse. For the known A = Rmxn, m <n and y E Rm, we make linear measurements y = Ax. To find such a signal x, one considers the following optimisation problem: minimize ||x||₁ subject to Ax = y where ||x||₁ = -₁ |xi|. i=1 Complete statements 1 and 2 to make them correct and decide whether statements 3, 4 and 5 are true or false. 1. We need decision variables to express the given instance as a linear programme. 2. We need inequality constraints to express the given instance as a linear programme. 3. Expressing the given instance as a linear programme allows us to solve instances in polynomial-time. 4. Using linear programming to model the given instance that require each element x; of this signal to be either zero or one, allows to solve such instances in polynomial-time. 5. For a feasible linear programme it is sufficient to search for optimum solutions along the boundary of the feasible region. n m n+1 2n m+n True False