Many techniques for finding approximate solutions for the matrix equation when it is overdetermined (i.e., when ) work by minimizing the 2-norm. This is because of certain advantages that make it computationally tractable. One reason is that the function

is differentiable and differentiation is a linear operation. Thus, a linear system can be formed that finds the minimizing solutions. Another reason is that the 2-norm is preserved under orthogonal transformations. This means that a range of equivalent problems can be formed, which may be easier to solve.

However, there are other solutions that can be found by minimizing other norms, such as the 1-norm or the -norm. These may be more desirable in the particular context because they may find solutions that maintain important properties relevant to the individual problem. In this example techniques are shown to find approximate solutions that minimize these norms; both will use a method to find minimum values of constrained linear problems; typically this is known as linear programming.

In Mathematica, linear programming is provided by the function LinearProgramming. This can solve the linear programming problem for the different types of numbers that Mathematica supports: integers and rational numbers, as well as machine-precision approximate real and arbitrary-precision approximate real numbers. In addition, it provides techniques that are suitable for minimizing extremely large systems by means of an interior point method.

The solutions given in this section are suitable for dense matrix input. It would be straightforward to modify them for sparse matrix input; this would be necessary to take full advantage of the interior point linear programming technique.

Note that the techniques in this section could be extended to add other constraints on the solution.

Minimizing the 1-norm involves finding the value of that minimizes the following.

This is done by forming new variables and finding the minimum.

This is implemented with the following program.

In[1]:=

This finds the solution.

In[2]:=

Out[4]=

Here 1-, 2-, and -norms for the solution that was found are computed.

In[5]:=

Out[5]=

Minimizing the -norm is similar to minimizing the 1-norm. It involves finding the value of that minimizes the following.

This is done by forming new variables and finding the minimum.

This is implemented with the following program.

In[1]:=

This finds the solution.

In[2]:=

Out[4]=

Here, 1-, 2-, and -norms for the solution that was found are computed.

In[5]:=

Out[5]=