higher order linear regression

Question

I have the matrix system:

A x B = C

A is a by n and B is n by b. Both A and B are unknown but I have partial information about C (I have some values in it but not all) and n is picked to be small enough that the system is expected to be over constrained. It is not required that all rows in A or columns in B are over constrained.

I'm looking for something like least squares linear regression to find a best fit for this system (Note: I known there will not be a single unique solution but all I want is one of the best solutions)

---

To make a concrete example; all the a's and b's are unknown, all the c's are known, and the ?'s are ignored. I want to find a least squares solution only taking into account the know c's.

[ a11, a12 ]                                     [ c11, c12, c13, c14, ?   ]
[ a21, a22 ]   [ b11, b12, b13, b14, b15]        [ c21, c22, c23, c24, c25 ]
[ a31, a32 ] x [ b21, b22, b23, b24, b25] = C ~= [ c31, c32, c33, ?,   c35 ]
[ a41, a42 ]                                     [ ?,   ?,   c43, c44, c45 ]
[ a51, a52 ]                                     [ c51, c52, c53, c54, c55 ]

---

Note that if B is trimmed to b11 and b21 only and the unknown row 4 chomped out, then this is almost a standard least squares linear regression problem.

Answer 1

This problem is illposed as described.

Let A, B, and C=5, be scalars. You are asking to solve a*b=5 which has an infinite number of solutions.

One approach, on the information provided above, is to minimize the function g defined as

g(A,B) = ||AB-C||^2 = trace((AB-C)*(AB-C))^2

using Newtons method or a quasi-secant approach (BFGS).
(You can easily compute the gradient here). M* is the transpose of M and multiplication is implicit. (The norm is the frobenius norm... I removed the underscore F as it was not displaying properly)

As this is an inherently nonlinear problem, standard linear algebra approaches do not apply.

If you provide more information, I may be able to help more.

---

Some more questions: I think the issue is here is that without more information, there is no "best solution". We need to determine a more concrete idea of what we are looking for. One idea, could be a "sparsest" solution. This area is a hot area of research, with some of the best minds in the world working here (See Terry Tao et al. work on Nuclear Norm) This problem although tractable is still hard.

---

Unfortunately, I am not yet able to comment, so I will add my comments here. As said below, LM is a great approach to solving this and is just one approach. along the lines of the Newton type approaches to either the optimization problem or the nonlinear solving problem.

Here is an idea, using the example you gave above: Lets define two new vectors, V and U each with 21 elements (exactly the same number of defined elements in C).

V is precisely the known elements of C, column ordered, so (in matlab notation)

V = [C11; C21; C31; C51; C12; .... ; C55]

U is a vector which is a column ordering of the product AB, LEAVING OUT THE ELEMENTS CORRESPONDING TO '?' in matrix C. Collecting all the variables into x we have
x = [a11, a21, .. a52, b11, b21 ..., b25].

f(x) = U (as defined above).

We can now try to solve f(x)=V with your favorite nonlinear least squares method.

As an aside, although a poster below recommended simulated annealing, I recommend against it. THere are some problems it works, but it is a heuristic. When you have powerful analytic methods such as Gauss-Newton or LM, I say use them. (in my own experience that is)