Compressed Sensing: Solving an Optimization Problem with Minimum l1 Norm

[maNoFchangE]

I finally got a problem in my reading, so my problem is I am given a matrix $A$, column vector $f$, and a relation $f = Ag$ where $g$ is a column vector. The dimensions of those vectors and matrices are such that the above matrix multiplication makes sense, that is $A$ is not necessarily square. My goal is to compute $g$ but the number of rows of $A$ is less than the number of columns so that the solution is not unique. However the sought solution is required to be minimum in its $l_1$ norm, where $l_1$ norm of $g$ is defined to be $||g||_1 = \Sigma_i^N |g_i|$, I guess some of you are familiar with this norm type from linear algebra.
The above problem is clearly an optimization problem, but as I know there are few types of optimization problem, so if you had recongnized such a problem can you tell me what type of optimization my problem belongs to? So that I can navigate directly to the right chapter in my textbooks.

 

[jvicens]

Thank you for sharing your problem with us. I can understand your frustration when faced with a challenging problem in your reading. It seems that you are dealing with a linear optimization problem, also known as linear programming. In this type of problem, the goal is to optimize a linear objective function (in your case, the $l_1$ norm of $g$) subject to linear constraints (in your case, the relation $f=Ag$).

Specifically, your problem falls under the category of constrained linear least squares problems. The objective is to minimize the $l_1$ norm of $g$ while satisfying the given relation. This can be solved using various optimization techniques such as the simplex method or the interior point method.

I hope this helps in your understanding of the problem and leads you to the right chapter in your textbooks. Best of luck in your studies!