Re: Question

------=_Part_1518104_2145308189.1747437907090
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

 If I understand your question, it appears that you are seeking a solution =
to a massively underdetermined system of linear equations, Ax=3Dy for which=
 the x vector is sparse with most elements being zero.

I spent 2013-2016 reading "A Mathematical Introduction to Compressive Sensi=
ng" by Foucart and Rauhut. Which required I read Mallat's "A Wavelet Tour o=
f Signal Processing" and then reread Foucart and Rauhut. Happily, it is eas=
ier to do than it is to understand. FWIW the 3 years included reading all t=
he original papers for a total of around 3000 pages. Non-trivial effort, bu=
t worth it just for the magic of it all. Best thing since Norbert Wiener in=
vented DSP.

The seminal paper is Donoho's 2004-9 proof that iff a sparse L1 solution to=
 Ax=3Dy exists it is the L0 solution. The requirement is that A possess the=
 Restricted Isometry Property. No combinations of any columns of A are corr=
elated. That is unavoidably L0. So all you can do is try to solve Ax=3Dy us=
ing linear programming. You are not guaranteed a solution, but if you get o=
ne it is probably the L0 solution.

I did quite a lot of work solving heat flow equations. I used awk to genera=
te huge GMPL files which I then ran with the command line solver. I did ten=
s of thousands of runs. Worked brilliantly.

Have Fun!
Reg


     On Friday, May 16, 2025 at 04:55:34 PM CDT, Federico Miyara <fmiyara@f=
ceia.unr.edu.ar> wrote: =20
=20
=20
I need to solve the following problem:

I have an alphabet of n symbols and a dictionary with N words of m
symbols (n in the order of tens, N in the order of tens of thousands, m
=3D 4, say)

Assuming each symbol has a definite probability, I need to generate a
list of M words (M in the order of 100) taken from the dictionary in
which the proportion of each symbol matches as best as possible the
required probability.

Is this a problem that can be solved using GLPK?

Thanks.

Bes regards,

Federico Miyara

--
Este correo electr=C3=B3nico ha sido analizado en busca de virus por el sof=
tware antivirus de Avast.
www.avast.com

 =20
------=_Part_1518104_2145308189.1747437907090
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div>                If I understand your question, it appears that you are=
 seeking a  solution to a massively underdetermined system of linear equati=
ons, Ax=3Dy for which the x vector is sparse with most elements being zero.=
<br><br>I spent 2013-2016 reading &quot;A Mathematical Introduction to Comp=
ressive Sensing&quot; by Foucart and Rauhut.  Which required I read Mallat&=
#39;s &quot;A Wavelet Tour of Signal Processing&quot; and then reread Fouca=
rt and Rauhut.  Happily, it is easier to do than it is to understand.  FWIW=
 the 3 years included reading all the original papers for a total of around=
 3000 pages.  Non-trivial effort, but worth it just for the magic of it all=
.  Best thing since Norbert Wiener invented DSP.<br><br>The seminal paper i=
s Donoho&#39;s 2004-9 proof that iff a sparse L1 solution to Ax=3Dy exists =
it is the L0 solution.  The requirement is that A possess the Restricted Is=
ometry Property.   No combinations of any columns of A are correlated.  Tha=
t is unavoidably L0.  So all you can do is try to solve Ax=3Dy using linear=
 programming.  You are not guaranteed a solution, but if you get one it is =
probably the L0 solution.<br><br>I did quite a lot of work  solving heat fl=
ow equations.  I used awk to generate huge GMPL files which I then ran with=
 the command line solver.  I did tens of thousands of runs.  Worked brillia=
ntly.<br><br>Have Fun!<br>Reg<br><br><br>            </div>            <div=
 class=3D"yahoo_quoted" style=3D"margin:10px 0px 0px 0.8ex;border-left:1px =
solid #ccc;padding-left:1ex;">                        <div style=3D"font-fa=
mily:'Helvetica Neue', Helvetica, Arial, sans-serif;font-size:13px;color:#2=
6282a;">                                <div>                        On Fri=
day, May 16, 2025 at 04:55:34 PM CDT, Federico Miyara &lt;[email protected]=
.edu.ar&gt; wrote:                    </div>                    <div><br></=
div>                    <div><br></div>                                    =
            <div><div dir=3D"ltr"><br></div><div dir=3D"ltr">I need to solv=
e the following problem:<br></div><div dir=3D"ltr"><br></div><div dir=3D"lt=
r">I have an alphabet of n symbols and a dictionary with N words of m<br></=
div><div dir=3D"ltr">symbols (n in the order of tens, N in the order of ten=
s of thousands, m<br></div><div dir=3D"ltr">=3D 4, say)<br></div><div dir=
=3D"ltr"><br></div><div dir=3D"ltr">Assuming each symbol has a definite pro=
bability, I need to generate a<br></div><div dir=3D"ltr">list of M words (M=
 in the order of 100) taken from the dictionary in<br></div><div dir=3D"ltr=
">which the proportion of each symbol matches as best as possible the<br></=
div><div dir=3D"ltr">required probability.<br></div><div dir=3D"ltr"><br></=
div><div dir=3D"ltr">Is this a problem that can be solved using GLPK?<br></=
div><div dir=3D"ltr"><br></div><div dir=3D"ltr">Thanks.<br></div><div dir=
=3D"ltr"><br></div><div dir=3D"ltr">Bes regards,<br></div><div dir=3D"ltr">=
<br></div><div dir=3D"ltr">Federico Miyara<br></div><div dir=3D"ltr"><br></=
div><div dir=3D"ltr">--<br></div><div dir=3D"ltr">Este correo electr=C3=B3n=
ico ha sido analizado en busca de virus por el software antivirus de Avast.=
<br></div><div dir=3D"ltr">www.avast.com<br></div><div dir=3D"ltr"><br></di=
v></div>            </div>                </div>
------=_Part_1518104_2145308189.1747437907090--