# Matching Pursuit Before Computer Science

Igor Carron -

Laurent, When you “was the determination of stresses in frameworks”, did you mean “was the determination of stresses in structures” or “was the determination of structural stress” ? Igor.

#### [jackdurden]( "laurent.jacques@epfl.ch") -

Actually, I was using the same terminology than the one of G. Temple in the beginning of his paper. I think that the real meaning is “the determination of stresses in structures” in the sense that they had to determine the motion of the equilibrium state of a network of spring (used as a model of the structure) under the application of external forces on the structure. In that context, if $x$ represents the vector of motion of the springs extremities, then, at the new equilibrium state reached when there exist external force $F=-b$, $Ax$ represents the Hooke’s law expressing the spring force w.r.t. the deviations $x$ (i.e. internal forces), so that $Ax + F = Ax - b = 0$ is the Newton’s first law that allows to find x. Laurent

#### [jackdurden]( "laurent.jacques@epfl.ch") -

I update the text in function of what I explained. Thank you Igor. That point was indeed unclear and it deserved a better explanation. Laurent

#### [Igor Carron](http://nuit-blanche.blogspot.com "igorcarron@gmail.com") -

Thanks for the explanation, it definitely provided some context that one could relate to. By the way, when reading the paper by Southwell, would there be a case where the physics allows for D to be a rectangular matrix leading to an undetermined system. Could some boundary conditions make the system undetermined for instance ? Cheers, Igor.

#### [jackdurden]( "laurent.jacques@epfl.ch") -

That’s a very interesting aspect. I cannot really answer but here are some (random) thoughts. Perhaps one possibility would be to stay with this structure model and continue to see the knowledge of the external forces as the measurements. So, you would not be required to know all the external forces applied to each spring, but only a few of them if you can assume than the spring motions (i.e. $\alpha_*$) are sparse. In that case, you could work with a random sub-sampling of the rows of $D$ (as a random subsampling of any orthogonal basis) and still be able to deduce $\alpha_*$. Interestingly, the non-zero entries of $D$ corresponds to the non-zero entries of the connectivity matrix of the springs, and the value of the non-zero entries are the spring constants of the Hooke’s model. In 2-D, this link with the connectivity could lead also to some interesting interpretations related to graph theory and measurement matrix (e.g. recent paper of Goldberg, Indyk and al.). But I’m not at all an expert on that topic and I’m perhaps wrong. Finally, in Temple’s paper, the system $D\alpha_*=s$, since inherited from Newton’s first law, has a connection with an “energy” description. Indeed, this system is valid when the energy $W=V_1+V_2$ formed with the usual spring potential energy $V_1 = \frac{1}{2}\alpha_*^T D \alpha_*$ and the (assumed constant) external forces potential $V_2= -s^T\alpha_*$ is minimum (equilibrium state). Temple created another Matching Pursuit like method (not explained in the post) to minimize as fast as possible this energy in the iterations. I’m very curious to see if such a (quadratic) energy concept can survive outside of this physical model as another theoretical element to minimize to find $\alpha_*$ in a CS formulation of the problem. But perhaps it is worthless since possibly just equivalent to a least square like minization problem. I don’t know. It is just some thoughts ;-) Laurent

#### [jackdurden]( "laurent.jacques@epfl.ch") -

Correction: $D$ is not the connectivity matrix but the Laplacian made with the connectivity matrix, i.e. the degree of the connectivity on the diagonal, and minus the connectivity on the off-diagonal elements. 