• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

what is the terminology for my problem? Hwo to solve?

B

beginner99

Diamond Member
I'm looking for the name for a certain problem to be able to google for solutions. (before trying to reinvent the wheel).

I have a bunch of "patterns" where pattern is just a list of a numeric type of fixed size.
Example:
Code: 
Pattern 1: 1,0,5,2
Pattern 2: 9,3,1,1
...
Pattern X: 8,6,2,0

I then have Pattern Z:
Code: 
 Pattern Z: 9,6,7,2

The problem is to now find the a combination of patterns that result in Pattern Z.
By combination I mean "adding together each element i of the different patterns"; "Sum of columns"

Eg. for this example:
Code: 
Pattern 1: 1,0,5,2
+
Pattern X: 8,6,2,0
=
Pattern Z: 9,6,7,2

How is this problem called?
 
Im not entirely sure i understand what youre asking, but it seems you might start by googling linear systems, or systems of linear equations.
 
homercles337 said:
Im not entirely sure i understand what youre asking, but it seems you might start by googling linear systems, or systems of linear equations.
Click to expand...

yeah, this looks like a linear algebra sort of problem. It will be a beast to solve in a reasonable amount of time with large X.
 
Cogman said:
yeah, this looks like a linear algebra sort of problem. It will be a beast to solve in a reasonable amount of time with large X.
Click to expand...

My X is fairly small (around 1000) and I played around with ejml a java library for such problems. very fast, almost instantaneous.

However after thinking some more I realized the actual problem is much more complex. In reality, the desired solution should only contain around 20-50 of those 1000 "columns". And a much bigger restriction is that contrary to my prior statement elements in x (= the solution vector) must all be between 0 and 1 and their sum must also be between 0 and 1.

I'm not a math wiz so I went to wiki which says that the number of combinations is:
http://en.wikipedia.org/wiki/Combination

for n=1000 and k = 40, with the windows calculator I get something like 5.6*10^71 combinations...if you also consider that 21,22,23,24,...50 are also valid k it's easy to see that the problem isn't really solvable at least in my life time.
 
beginner99 said:
I'm looking for the name for a certain problem to be able to google for solutions. (before trying to reinvent the wheel).

I have a bunch of "patterns" where pattern is just a list of a numeric type of fixed size.
Example:
Code: 
Pattern 1: 1,0,5,2
Pattern 2: 9,3,1,1
...
Pattern X: 8,6,2,0

I then have Pattern Z:
Code: 
 Pattern Z: 9,6,7,2

The problem is to now find the a combination of patterns that result in Pattern Z.
By combination I mean "adding together each element i of the different patterns"; "Sum of columns"

Eg. for this example:
Code: 
Pattern 1: 1,0,5,2
+
Pattern X: 8,6,2,0
=
Pattern Z: 9,6,7,2

How is this problem called?
Click to expand...

Break down the problem into smaller, more manageable problems.

Instead of trying to solve the whole problem at once, take the first number from each of the "patterns" and work with that.

Given a list of numbers, a1, a2, a3...an, get the set of pairs that add up to x1. From there, toss out the rows that don't belong in the set.

Use the new set of rows to find a new set of pairs that add up to x2. Then rinse and repeat.

The trick is to work with a subset of rows for every generation forward to reduce the search space.

Another hint: If you know the range of the values you are looking for (ie, I know pattern Z can only be 0-9), then you can generate a lookup table that contains the valid set of pairs of numbers. From there, you can search through your row's element and pick out the sets.
 
Last edited:
One of my favorite math classes in college. Math Models. I recommend it to any computer programmer.

I don't know where to classify what you're talking about? You need to explicitly define your constraints for it to fit into any one type of system. (linear, deterministic, random, etc)

Are you only attempting to find set of characteristic equations for the columns or do the rows have some restriction upon the system?

Do all points in the system have to be equally spaced, and for that matter exist?

The more random points you place in a system the less chance of finding a solution. (convergence vs divergence)
 
Last edited:
Schmide said:
One of my favorite math classes in college. Math Models. I recommend it to any computer programmer.

I don't know where to classify what you're talking about? You need to explicitly define your constraints for it to fit into any one type of system. (linear, deterministic, random, etc)

Are you only attempting to find set of characteristic equations for the columns or do the rows have some restriction upon the system?

Do all points in the system have to be equally spaced, and for that matter exist?

The more random points you place in a system the less chance of finding a solution. (convergence vs divergence)
Click to expand...

The real problem behind it is as follows:

You have components. You measure them on different sensors. the signals from the sensors is 1 column in the matrix.
You have a mixture. You measure it over the same sensors. Now you want to create the same (or similar) signal as that mixture using your set of components.

Because you measure the pure component you can't get a stronger signal than measured (eg. max. 1 in solution vector) and you can't have less than 0.
There are more potential constraints which narrow down the possible solutions but makes it a lot harder to find any solution.
 
If you're doing signal processing, you want to read up on Fourier analysis.

The basics of it is representing a signal as the sum of oscillating functions (sin, cos, e^ix).

With them and their brethren you can do all kinds of cool stuff. (noise removal, equalization, signal rectifying, etc)

It's kind of hard but there are a lot of libraries out there. No need to reinvent the wheel.
 
Now youre talking about signal mixing? Youre very confused about what you are doing. If you are observing mixed signals, and want to separate them, look into blind source separation (BSS), projection pursuit, or independent components analysis (ICA).
 
I'm not confused what I'm doing. Just how to solve the problem. No it is not signal processing but the data is from real physical measurements. I see now that my post might have been confusing.
 
The 0 to 1 is just a matter of scaling. Rescale it so that 0 is 0 and 1 is 65535. Then you have numbers on which you can perform 16 bit unsigned integer math. That gets rid of the floating points and will make things much faster. What you're doing sounds pretty simple, as long as you are only dealing with 4 element arrays. You just have to have the logic skills, I doubt anyone can really help you unless you get more specific. I work in measurement control and have done my fair share of signal processing.
 
I can't get specific for certain reasons...confidentiality and so...

Schmide said:
This is a contradiction.

Processing data is from real physical measurements is signal processing.
Click to expand...

How can i formulate it? I'm doing something with the already processed, finished measurement. With the data from that measurement the idea is to make predictions.


sm625 said:
The 0 to 1 is just a matter of scaling. Rescale it so that 0 is 0 and 1 is 65535. Then you have numbers on which you can perform 16 bit unsigned integer math. That gets rid of the floating points and will make things much faster. What you're doing sounds pretty simple, as long as you are only dealing with 4 element arrays. You just have to have the logic skills, I doubt anyone can really help you unless you get more specific. I work in measurement control and have done my fair share of signal processing.
Click to expand...

rescaling is of course possible but it does not narrow the possible amount of solutions and how to find a fitting one. See prior post. the array is 20-50 x 1000 elements and those 20-50 elements can be combined in any way from about 1000 different elements -> over 10^72 possible solutions for each single "prediction".
 
beginner99 said:
How can i formulate it? I'm doing something with the already processed, finished measurement. With the data from that measurement the idea is to make predictions.

rescaling is of course possible but it does not narrow the possible amount of solutions and how to find a fitting one. See prior post. the array is 20-50 x 1000 elements and those 20-50 elements can be combined in any way from about 1000 different elements -> over 10^72 possible solutions for each single "prediction".
Click to expand...

Again at least look into a signal processing library or technique. Say for instance you may have an anomalous datum, a noise reduction may be needed. Feature extraction could help determine an alphabet for your data allowing you to not only fill in the gaps, but also make future predictions. If you find an oscillating function, factoring it out may help reveal other characteristics. Wavelets can be useful as well. And so on...

Signal processing is basically reducing data to its fundamental elements, then reorganizing, factoring, translating them.
 
Schmide said:
One of my favorite math classes in college. Math Models. I recommend it to any computer programmer.

I don't know where to classify what you're talking about? You need to explicitly define your constraints for it to fit into any one type of system. (linear, deterministic, random, etc)

Are you only attempting to find set of characteristic equations for the columns or do the rows have some restriction upon the system?

Do all points in the system have to be equally spaced, and for that matter exist?

The more random points you place in a system the less chance of finding a solution. (convergence vs divergence)
Click to expand...

Do you remember what text book you guys used?
 
I graduated college in 1992 so no. I remember it being small and green but by now it would be woefully outdated.

The other great similar course back in the day was Numerical Analysis.
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top