Re: Question
Reginald Beardsley <[email protected]> Fri, 16 May 2025 23:53:09 +0000 (UTC)
| Newsgroups | gmane.comp.gnu.glpk |
|---|---|
| Message-ID | <[email protected]> |
------=_Part_1520843_534176552.1747439589885 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable FWIW I have a personal interest in the same problem as applied to decoding= Morse radiotelegraphy in the case of N >> S. I'd like to invite any interested in this particular problem to join the qe= [email protected] list. A detailed discussion of the problem on that list is most= welcome. It's a really cool application of linear programming and GLPK and= an active interest of mine. Have Fun! Reg On Friday, May 16, 2025 at 06:25:42 PM CDT, Reginald Beardsley <pulask= [email protected]> wrote: =20 =20 If I understand your question, it appears that you are seeking a solution= to a massively underdetermined system of linear equations, Ax=3Dy for whic= h 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_1520843_534176552.1747439589885 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <div> FWIW I have a personal interest in the same problem as= applied to decoding Morse radiotelegraphy in the case of N >> S.<br>= <br>I'd like to invite any interested in this particular problem to jo= in the [email protected] list. A detailed discussion of the problem on that l= ist is most welcome. It's a really cool application of linear program= ming and GLPK and an active interest of mine.<br><br>Have Fun!<br>Reg<br><b= r> </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-family:'Helvetica Neue', Helvetica, Arial= , sans-serif;font-size:13px;color:#26282a;"> = <div> On Friday, May 16, 2025 at 06:25:42 PM CDT, R= eginald Beardsley <[email protected]> wrote: </d= iv> <div><br></div> <div><br></div> = <div><div id=3D"yiv7444339516= "><div><div> 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 bein= g zero.<br clear=3D"none"><br clear=3D"none">I spent 2013-2016 reading "A M= athematical Introduction to Compressive Sensing" by Foucart and Rauhut. Wh= ich required I read Mallat's "A Wavelet Tour of Signal Processing" and then= reread Foucart and Rauhut. Happily, it is easier to do than it is to unde= rstand. FWIW the 3 years included reading all the original papers for a to= tal of around 3000 pages. Non-trivial effort, but worth it just for the ma= gic of it all. Best thing since Norbert Wiener invented DSP.<br clear=3D"n= one"><br clear=3D"none">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 requirem= ent is that A possess the Restricted Isometry Property. No combinations o= f any columns of A are correlated. That is unavoidably L0. So all you can= do is try to solve Ax=3Dy using linear programming. You are not guarantee= d a solution, but if you get one it is probably the L0 solution.<br clear= =3D"none"><br clear=3D"none">I did quite a lot of work solving heat flow e= quations. 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 brilliantly= .<br clear=3D"none"><br clear=3D"none">Have Fun!<br clear=3D"none">Reg<br c= lear=3D"none"><br clear=3D"none"><br clear=3D"none"> </div> = <div id=3D"yiv7444339516yqt74416" class=3D"yiv7444339516yqt858376385= 6"><div style=3D"margin:10px 0px 0px 0.8ex;border-left:1px solid #ccc;paddi= ng-left:1ex;" class=3D"yiv7444339516yahoo_quoted"> <= div style=3D"font-family:'Helvetica Neue', Helvetica, Arial, sans-serif;fon= t-size:13px;color:#26282a;"> <div> = On Friday, May 16, 2025 at 04:55:34 PM CDT, Federico Miyara &= lt;[email protected]> wrote: </div> = <div><br clear=3D"none"></div> <div><br clear= =3D"none"></div> <div><div d= ir=3D"ltr"><br clear=3D"none"></div><div dir=3D"ltr">I need to solve the fo= llowing problem:<br clear=3D"none"></div><div dir=3D"ltr"><br clear=3D"none= "></div><div dir=3D"ltr">I have an alphabet of n symbols and a dictionary w= ith N words of m<br clear=3D"none"></div><div dir=3D"ltr">symbols (n in the= order of tens, N in the order of tens of thousands, m<br clear=3D"none"></= div><div dir=3D"ltr">=3D 4, say)<br clear=3D"none"></div><div dir=3D"ltr"><= br clear=3D"none"></div><div dir=3D"ltr">Assuming each symbol has a definit= e probability, I need to generate a<br clear=3D"none"></div><div dir=3D"ltr= ">list of M words (M in the order of 100) taken from the dictionary in<br c= lear=3D"none"></div><div dir=3D"ltr">which the proportion of each symbol ma= tches as best as possible the<br clear=3D"none"></div><div dir=3D"ltr">requ= ired probability.<br clear=3D"none"></div><div dir=3D"ltr"><br clear=3D"non= e"></div><div dir=3D"ltr">Is this a problem that can be solved using GLPK?<= br clear=3D"none"></div><div dir=3D"ltr"><br clear=3D"none"></div><div dir= =3D"ltr">Thanks.<br clear=3D"none"></div><div dir=3D"ltr"><br clear=3D"none= "></div><div dir=3D"ltr">Bes regards,<br clear=3D"none"></div><div dir=3D"l= tr"><br clear=3D"none"></div><div dir=3D"ltr">Federico Miyara<br clear=3D"n= one"></div><div dir=3D"ltr"><br clear=3D"none"></div><div dir=3D"ltr">--<br= clear=3D"none"></div><div dir=3D"ltr">Este correo electr=C3=B3nico ha sido= analizado en busca de virus por el software antivirus de Avast.<br clear= =3D"none"></div><div dir=3D"ltr">www.avast.com<br clear=3D"none"></div><div= dir=3D"ltr"><br clear=3D"none"></div></div> </div> = </div></div></div></div></div> </div> </div> ------=_Part_1520843_534176552.1747439589885--