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.

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?

share|improve this question
    
As formulated, this sounds like a fairly standard linear programming problem in the $n$ variables $a_k$, with $256^2$ linear constraints $X_{ij} - \sum_k a_k (A_k)_{ij} \ge 0$ for $i,j\in\{1,\ldots,256\}$. However, if what you to know is how much $X$ is similar to each of the $A_k$ matrices, you may want to consider a least-squares projection of $X$ on the basis spanned by the $A_k$ instead. –  Rahul Jul 31 '12 at 18:58

2 Answers 2

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.

share|improve this answer
    
I know that this is linear programming problem that can be solved by general algorithm, I'm looking for 1. simplified, approximate or more specialized algorithms; 2. software implementations; 3 other approaches (like in the comment). –  Vi0 Jul 31 '12 at 19:52
    
1. Linear programming is about as simple as constrained optimization gets :). One way to greatly simplify the problem would be if you don't need $R$ to have nonnegative entries (in which case you can find a solution that minimizes the sum of squared entries by solving a linear system). 2. There are tons of LP implementations. What programming language are you using? For instance here is a C++ open-source implementation: projects.coin-or.org/Clp. Have you tried Googling "linear programming open source (name of language)"? –  user7530 Jul 31 '12 at 21:42
    
lpsolve is another free LP implementation, and if you have money to throw at the problem, I can recommend CPlex. –  Johannes Kloos Aug 1 '12 at 9:29
    
Octave has a nice interface to the GLPK (GNU Linear Programming Kit). Just as this –  Peter Sheldrick Nov 25 '12 at 15:18

Also considering simple "ad-hoc" algorithm:

  1. 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")
  2. 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".
  3. 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?

share|improve this answer
    
You haven't told us why you've chosen to use this instead of looking into the many linear programming solvers out there, so it's impossible for me to say whether what you're doing is a good idea or not. –  Rahul Aug 1 '12 at 2:23
    
Because of 1. implementing this may be easier than using solver (unsure); 2. Can manually adjust and hack each step and do domain-specific optimizations; 3. Unsure about how fast solvers does work and are they suited for tasks with many values. Actually I'm still thinking about various variants (my, solvers, "least-square projection"), so any ideas can be useful. –  Vi0 Aug 1 '12 at 8:56

Your Answer

 
discard

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.