What algorithms and/or software libraries should I use to solve this? I'm trying to write simple data format recognition program (that shows "what things does this unknown uncompressed unencrypted file have inside and where that things are located in the file") and it needs algorithm to solve the following thing:
Suppose $A_1, ... , A_n$ are input matrices.
For input matrix $X$ I should find $a_1, ..., a_n$ that brings
$R = X - a_1 A_1 - ... - a_n A_n$ to minimum (for example, using sum of elements as norm).
All involved matrices, including $R$ have only positive elements.
Each $A_i$ is a piece of statistic (256x256 matrix of "what probability of byte $i$ following byte $j$") for predefined sample data and $a_i$ should show how much of $A_i$'s trait there is in $X$'s data block.
Are there any known efficient (maybe approximate) algorithms to do this? Are there any simple (i.e. not a binding to some big mathematical framework) open source software libraries to avoid manual implementation?
 A: Let $M$ be a matrix whose columns are the matrices $A_i$, stretched out into one long column vector. Then you are looking for a minimizer $a$ of $f(Ma-x)$ for some objective $f(v)$. For minimizing sum of elements, $f(v) = \mathbf{1}\cdot v$.
You then want to solve the variational problem
$$\min_a\ (\mathbf{1}^T M)a\qquad \textrm{s.t.}\qquad Ma-x \leq 0.$$
This is just a linear programming problem (linear objective with linear inequality constraints). I can't recommend a free, lightweight LP package offhand, but I'm sure several exists in several languages.
A: Also considering simple "ad-hoc" algorithm:


*

*For each $k$ and $j$ find $r_{k,j}$ that minimizes $A_j - r_{k,j} A_k$ (preserving positiveness of all coordinates). It means how much of $A_j$ we have in $A_k$ (like "any/random data" have "text file" have "XML file" have "MediaWiki XML dump")

*For each $k$ find $a_k$ that makes $X - a_k A_k \rightarrow min$ while preserving all coordinates positive. Means "how much of $k$'s sample do we have in the input".

*From each $a_k$ subtract $\displaystyle\max_{j} r_{k,j} a_j$ and report it as "measure of containment of $k$'th sample in your data". Subtracting the most feasible "parent" sample's result is to prevent overshadowing more specific results like "mediawiki XML dump" with just general "xml file" or "ascii text".


Each step is simple to calculate and have domain-specific meaning. Is it a good idea or I should "think more" and/or use something else?
