lsqr constraints

I am trying to solve the system of linear equations Ax=b for x by iterative least square method(using lsqr code). How can I impose constraints to solutions x like none of x are zeros and negative numbers but sum of solutions x should be unity. In the matlab help, I found preconditioners(M or M=M1*M2) and initial guess(x0). I am not sure what they are and how should I set up them.Also I am not sure which is the best solution as i can get different converged solutions with different set of tol and maxit.Can I get help on these issues with a simple example? Thanks in advance!!

Answer 1

[Walter Roberson]

Perhaps if you used lsqlin() with the Aeq being a row vector of 1's the same length as x, and with Beq being the scalar 1. Since x is a column vector, the row vector of 1's matrix-multiplied by x would be the same thing as summing the x, and you would then compare that sum to what you had set for Beq, namely 1. You would use [] for A and b parameters, and you would use eps(0) for each of the lower bounds in order to require that the x are strictly positive.

[elham sa]

I have the exact same problem as described here, but lsqlin does not accept a function handle as the input matrix C. Does it?? If I do not have an explicit matrix C, and constraints as explained here, what other Matlab functions are suitable??

Thanks!

[Walter Roberson]

What do you have?

[elham sa]

I have a linear system to solve for a blur kernel:

||origImg * kernel - blurryImg ||

by * I mean "convolution". I have defined Ax and A'x as operator for convolution. [A represents the matrix form of the original image, x represents the blur kernel]

I have the original image and the blurry image, and would like to find the blur kernel. I know that the least square is not the best solution for this, but this is my starting point, and I will add regularizations to it.

My problem is "blur kernel" has to be non-negative, and I can not impose this constraint in lsqr function. lsqlin has this capability, but it only accepts an explicit matrix, not a function handle.

I appreciate you help!

Answer 2

[John D'Errico]

1. LSQR cannot apply linear equality constraints. Initial guess and preconditioners are completely different. They do not apply to your problem.

2. LSQR cannot solve a problem with bound constraints.

Software does what it is designed to do. That you want it to solve a different problem is not relevant. If you want to solve a problem with bound constraints AND an equality constraint then you will need to use LSQLIN, or something like it. (Yes, you could use lsqnonneg to bound the unknowns above zero, but the sum equality constraint will be a problem for you.)

[elham sa]

Thank you John for your answer.

I understand that LSQR is not designed for my application here. My question is : "Does LSQLIN accept function handles instead of the explicit matrix C?". As far as I know it doesn't. So "Is there an equivalent to lsqlin that accepts function handles?"

[John D'Errico]

No. LSQLIN does not accept general function handles. You may think of this as a linear problem, but in reality, all you are providing is a black box if it is a function handle. That means you would normally use a tool that will linearize things for you by differentiating that black box. So tools like fmincon or even lsqnonlin would make sense. Those tools are in fact the equivalent to lsqlin that I think you have asked for, and they will take general function handles, as well as allow the bound constraints you have suggested.

Alternatively, you could expand the convolution as a (sparse) linear system, writing out the equations as a matrix of coefficients. Then you could use lsqlin.

[elham sa]

Thank you very much John! Thanks for mentioning fmincon and the group of non-linear optimizers that I should be able to use in my application.

About the expansion to sparse linear system, actually that's what I'm doing right now, but it takes a long time for large images.

I appreciate your help!