Thread Subject: Least squares- infinity anf first norm minimization

Hi all,
I have an overdetermined system. I know how to solve it using L2 norm minimization but I am not sure how to use L-infinity (or L-1) norm minimization to get the solution. Does MATLAB has any function which can solve least square problem with L1 or L-infinity norm minimization?

Thanks!

> Does MATLAB has any function which can solve least square problem with L1 or L-infinity norm minimization?

Yes: LINPROG from optimization toolbox. You need to work out a little bit with slacks variables to transform your problem into linear programming problem.

PS: "least squares" means "L2", no more no less no fantasy...

Bruno

Thanks for your response.
I am not sure what would be the best way to solve the problem I have. Right now, I am using PINV function of MATLAB to solve my problem, which I assume is a least square approach (hence minimizes norm 2). I want a solution where norm "infinity" or "1" is minimized. Is that possible in MATLAB?

Following is an example of what I am trying to do:

I break my matrix into a product of phi and alpha using decomposition and get the following equation:

F=phi*alpha

F is a rectangular matrix (nxm), phi is also rectangular matrix of same size(nxm) and alpha is a square matrix (mxm)

e.g.
F=[1 2;
     3 6;
     4 5];

Now I create a new column for F_new (e.g [8;7]). and try to find corresponding values for alpha for this new column of F using PINV as follows,

alpha_new = pinv(phi) * F_new

If F and phi are square matrices, I recover the exact solution but if they are rectangular matrices, then I get a overdetermined system therefore the values are approximate.

My problem is to solve this overdetermined system using L infinity and L1 norm minimization to see if the results differ from L2 norm minimization.

Thanks a lot for ur help!

Sorry for top-posting, but if anybody can give me some pointers, I will really appreciate!!

Thanks.

"Balwinder Singh" <balwindersingh@gmail.com> wrote in message <hei2d3$ls9$1@fred.mathworks.com>...
> Sorry for top-posting, but if anybody can give me some pointers, I will really appreciate!!

I think I understood your question correctly, so my suggestion stands: LINPROG is the right pointer, and may be the only option to solve such "flat-norm" minimization with a built-in Matlab function.

Bruno

Thanks Bruno.

I found scripts online for solving a linear system for infinity and one norm. I am not sure whether the script is alright as I can't cross check it. Following are the scripts:

% input
m = 16; n = 8;
A = randn(m,n);
b = randn(m,1);

% infinity norm
f = [ zeros(n,1); 1 ];
Ane = [ +A, -ones(m,1) ; ...
             -A, -ones(m,1) ];
bne = [ +b; -b ];
xt = linprog(f,Ane,bne);
x_lp = xt(1:n,:);

%One Norm
f = [ zeros(n,1); ones(m,1); ones(m,1) ];
Aeq = [ A, -eye(m), +eye(m) ];
lb = [ -Inf*ones(n,1); zeros(m,1); zeros(m,1) ];
xzz = linprog(f,[],[], Aeq,b,lb,[]);
x_lp = xzz(1:n,:);


Do they look alright?


Thanks!!

"Balwinder Singh" <balwindersingh@gmail.com> wrote in message <hejfck$rkd$1@fred.mathworks.com>...
> Thanks Bruno.
>
> I found scripts online for solving a linear system for infinity and one norm. I am not sure whether the script is alright as I can't cross check it. Following are the scripts:
>
> % input
> m = 16; n = 8;
> A = randn(m,n);
> b = randn(m,1);
>
> % infinity norm
> f = [ zeros(n,1); 1 ];
> Ane = [ +A, -ones(m,1) ; ...
> -A, -ones(m,1) ];
> bne = [ +b; -b ];
> xt = linprog(f,Ane,bne);
> x_lp = xt(1:n,:);
>
> %One Norm
> f = [ zeros(n,1); ones(m,1); ones(m,1) ];
> Aeq = [ A, -eye(m), +eye(m) ];
> lb = [ -Inf*ones(n,1); zeros(m,1); zeros(m,1) ];
> xzz = linprog(f,[],[], Aeq,b,lb,[]);
> x_lp = xzz(1:n,:);
>
>
> Do they look alright?
>

Very quick look yes, they look alright.

Bruno

Thanks a lot Bruno!! I really appreciate your help!