Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given $C=XF$, and only data for $C$, solving for $X$ and $F$ has been described as not tractable (which I'm content to believe, but others aren't). If that's the case, where does the following argument fall apart?

Suppose $C^i=XF^i$ is written: $\begin{bmatrix} C_1^i \\ \vdots \\ C_m^i \end{bmatrix} = \begin{align}\begin{bmatrix} X_{1,1} & \dots & X_{1,n} \\ \vdots & & \vdots \\ X_{m,1} & \dots & X_{m,n} \end{bmatrix}\end{align}\begin{bmatrix} F_1^i \\ \vdots \\ F_n^i \end{bmatrix}$

One instance of data for a given $i$ of $C^i$ would produce $m$ equations and $mn+n$ unknowns.

$q$ instances of data for $C^i$ would produce $qm$ equations and $mn+qn$ unknowns.

If the supposition that you need more equations than unknowns is sufficient, why can I contradict others statements of not tractability by choosing whole number values to satisfy the inequality:

$qm >= mn+qn$?

Using say $q=6,m=3,n=2$.

share|improve this question
How do you get "instances of $C$"? If $X$ and $F$ are unknown but you are looking for a particular solution, then there is only one $C$; if by "instance" you mean an entry, then you can get at most $m$ instances. Finally, "More equations than unknowns" is a sufficient condition for the existence of nontrivial solutions to a homogenous system of linear equations. Here, you do not have a homogeneous system, and your equations are not homogeneous (unknowns are multiplying each other). So why would you believe that "more equations than unknowns is sufficient"? –  Arturo Magidin Sep 6 '10 at 5:01
Well, I did write "If". I didn't want to repeat the information in the linked question, but I'll edit for the casual reader. I hope that helps clear up the presentation of "instances of data". –  Jamie Sep 6 '10 at 5:12
It's ill-poised if you only know $C$; there are too many possible $(X, F)$ pairs that can be associated with your $C$ if at least one component of $C$ is nonzero. –  J. M. Sep 6 '10 at 5:28
add comment

1 Answer

up vote 1 down vote accepted

I don't think there's a general definition of tractability in the sense you probably mean, other than "unsolvable under the given conditions"; however "given conditions" are very important. In practice conditions on a theorem aren't set beforehand but typically arise from working on the problem - you want to show X, but find out that X doesn't hold unless you also make assumption Y, and so then you ask yourself if Y is a reasonable thing to assume in the problem setting you are interested in. In the end you (hopefully) prove a theorem that has as few assumptions as you can get away with, and still is useful for the problem you are interested in.

Now, there is a clear distinction between the two situations "can I very likely get a practically satisfactory solution to (some impossible problem) if I add some extra constraints by applying domain knowledge" and "can I solve a problem that can be proved to be impossible in general". In your previous post, the problem you gave was impossible in general, but a good enough solution was tractable under mild assumptions. So, tractability is a function of how you choose to work on a problem, and specifically of which conditions or constraints you assume to hold/are happy to accept in the first place.

I can recommend Imre Lakatos's "Proofs and Refutations", which makes this point better than I could ever hope to and, IMHO, is one of those books that every intelligent person should read at sometime in their life.

share|improve this answer
I should also probably add, that whether a solution exists or not also depends on what you are prepared to accept as a solution too. Re your earlier post, in the case of ICA you still have infinitely many solutions since (a) you can't say which source gave which signal and (b) you can't say anything about their relative amplitudes. However, if you are only after the individual signals (and scaling and order don't matter), then ICA is a state-of-the-art method for solving that particular problem. –  Bob Durrant Sep 6 '10 at 17:07
Thank-you for posting such clear explanations. –  Jamie Sep 13 '10 at 15:18
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.