5 ms·

Taking the inverse of a matrix only solves problems which can be described in a specific way. There are situations where you want to optimize an arbitrary funct

by xaedes 10y ago

Taking the inverse of a matrix only solves problems which can be described in a specific way. There are situations where you want to optimize an arbitrary function. Also taking the inverse of a matrix isn't always easy. For example for very large matrices. The are also problems where the optimal solution changes over time (e.g. trajectory following control). This gives a good guess for the solution at each timestep(t>0) and improving that with gradient descent can be more performant than completely solving for a matrix inverse each time.

pmarreck 10y ago
> Also taking the inverse of a matrix isn't always easy. For example for very large matrices. Yeah, I know. I am saying that I think there is probably an undiscovered solution to doing faster inverse matrices, based on occam's razor (which I'm taking to mean that "complex and ugly" suggests there is probably undiscovered "simpler and more elegant"... which I've seen over and over again in other areas... gradient descent being the "complex and ugly" here) > This gives a good guess for the solution at each timestep(t>0) and improving that with gradient descent can be more performant than completely solving for a matrix inverse each time. That's a good point, but perhaps the hypothetical matrix inversion I'm assuming exists also allows you to do computationally efficient differential inversions based on small changes to the matrix. I admit this was just a "gut feeling," but when I first learned about gradient descent vs. matrix inversion I had a very strong gut feeling that there was a better way out there. My career is programming (where I have followed this "gut feeling" many times, usually to success) and I did papers on matrices and determinants in high school, this may be informing my "gut". Not sure if any mathy people are reading this, but I think there's gold to be had here, if you look hard enough
- RBerenguel 10y ago
  Golub/van Loan (Matrix Computations) is a thick book talking only on methods to work with matrices, old... And not "much" has changed in the basics. If there is gold to be had there, is damn deep, and won't be an easy algorithm at all
- maxerize 10y ago
  Gradient descent is neither complex nor ugly, it's the most immediate and straightforward way of searching for extrema. Iterative methods in general might be your only shot if the problem is not linear and linearisation is not an option. From a practical point of view, iterative methods in general allow you to terminate on your own terms, whereas many direct methods don't have a useful representation at hand to return prematurely.
- math_and_stuff 10y ago
  Many, many, very smart people have worked on exactly this problem and the result is a large, somewhat disjoint, family of techniques for forming/applying approximate inverses in subquadratic time for delicate families of matrices (e.g., discretizations of elliptic partial differential equations). Keep in mind that many linear systems can be solved in near linear time despite the inverse being dense.
  - pmarreck 10y ago
    > Many, many, very smart people have worked on exactly this problem If I applied this logic to anything genuinely new that was ever discovered, then nothing genuinely new would ever be discovered. I don't know what the fallacy there is, but it must be one. Modern example: Many, many, MANY people worked on globally disparate data synchronization (consensus) problems (Raft, Paxos were some solutions), while ensuring their security, and then Bitcoin came along. Bitcoin hasn't been hacked (although its exchanges have). I'm just saying my gut says there's more to discover there.
- deleted 10y ago
  [deleted]
- GFK_of_xmaspast 10y ago
  I think your gut feeling needs some serious recalibration. Please consider "the Hilbert matrix" (http://blogs.mathworks.com/cleve/2013/02/02/hilbert-matrices/ http://blogs.mathworks.com/cleve/2013/02/02/hilbert-matrices...) and more generally condition numbers (https://en.wikipedia.org/wiki/Condition_number https://en.wikipedia.org/wiki/Condition_number), and in regards to "computationally efficient differential inversions based on small changes to the matrix", consider what happens to a polynomial's roots when you make small changes in the coefficients.

by xaedes 10y ago

pmarreck 10y ago

> Also taking the inverse of a matrix isn't always easy. For example for very large matrices. Yeah, I know. I am saying that I think there is probably an undiscovered solution to doing faster inverse matrices, based on occam's razor (which I'm taking to mean that "complex and ugly" suggests there is probably undiscovered "simpler and more elegant"... which I've seen over and over again in other areas... gradient descent being the "complex and ugly" here) > This gives a good guess for the solution at each timestep(t>0) and improving that with gradient descent can be more performant than completely solving for a matrix inverse each time. That's a good point, but perhaps the hypothetical matrix inversion I'm assuming exists also allows you to do computationally efficient differential inversions based on small changes to the matrix. I admit this was just a "gut feeling," but when I first learned about gradient descent vs. matrix inversion I had a very strong gut feeling that there was a better way out there. My career is programming (where I have followed this "gut feeling" many times, usually to success) and I did papers on matrices and determinants in high school, this may be informing my "gut". Not sure if any mathy people are reading this, but I think there's gold to be had here, if you look hard enough

RBerenguel 10y ago
Golub/van Loan (Matrix Computations) is a thick book talking only on methods to work with matrices, old... And not "much" has changed in the basics. If there is gold to be had there, is damn deep, and won't be an easy algorithm at all
maxerize 10y ago
Gradient descent is neither complex nor ugly, it's the most immediate and straightforward way of searching for extrema. Iterative methods in general might be your only shot if the problem is not linear and linearisation is not an option. From a practical point of view, iterative methods in general allow you to terminate on your own terms, whereas many direct methods don't have a useful representation at hand to return prematurely.
math_and_stuff 10y ago
Many, many, very smart people have worked on exactly this problem and the result is a large, somewhat disjoint, family of techniques for forming/applying approximate inverses in subquadratic time for delicate families of matrices (e.g., discretizations of elliptic partial differential equations). Keep in mind that many linear systems can be solved in near linear time despite the inverse being dense.
- pmarreck 10y ago
  > Many, many, very smart people have worked on exactly this problem If I applied this logic to anything genuinely new that was ever discovered, then nothing genuinely new would ever be discovered. I don't know what the fallacy there is, but it must be one. Modern example: Many, many, MANY people worked on globally disparate data synchronization (consensus) problems (Raft, Paxos were some solutions), while ensuring their security, and then Bitcoin came along. Bitcoin hasn't been hacked (although its exchanges have). I'm just saying my gut says there's more to discover there.
deleted 10y ago
[deleted]
GFK_of_xmaspast 10y ago
I think your gut feeling needs some serious recalibration. Please consider "the Hilbert matrix" (http://blogs.mathworks.com/cleve/2013/02/02/hilbert-matrices/ http://blogs.mathworks.com/cleve/2013/02/02/hilbert-matrices...) and more generally condition numbers (https://en.wikipedia.org/wiki/Condition_number https://en.wikipedia.org/wiki/Condition_number), and in regards to "computationally efficient differential inversions based on small changes to the matrix", consider what happens to a polynomial's roots when you make small changes in the coefficients.