nhaliday + linear-algebra   94

Bareiss algorithm - Wikipedia
During the execution of Bareiss algorithm, every integer that is computed is the determinant of a submatrix of the input matrix. This allows, using the Hadamard inequality, to bound the size of these integers. Otherwise, the Bareiss algorithm may be viewed as a variant of Gaussian elimination and needs roughly the same number of arithmetic operations.
nibble  ground-up  cs  tcs  algorithms  complexity  linear-algebra  numerics  sci-comp  fields  calculation  nitty-gritty 
june 2019 by nhaliday
ON THE GEOMETRY OF NASH EQUILIBRIA AND CORRELATED EQUILIBRIA
Abstract: It is well known that the set of correlated equilibrium distributions of an n-player noncooperative game is a convex polytope that includes all the Nash equilibrium distributions. We demonstrate an elementary yet surprising result: the Nash equilibria all lie on the boundary of the polytope.
pdf  nibble  papers  ORFE  game-theory  optimization  geometry  dimensionality  linear-algebra  equilibrium  structure  differential  correlation  iidness  acm  linear-programming  spatial  characterization  levers 
may 2019 by nhaliday
Complexity no Bar to AI - Gwern.net
Critics of AI risk suggest diminishing returns to computing (formalized asymptotically) means AI will be weak; this argument relies on a large number of questionable premises and ignoring additional resources, constant factors, and nonlinear returns to small intelligence advantages, and is highly unlikely. (computer science, transhumanism, AI, R)
created: 1 June 2014; modified: 01 Feb 2018; status: finished; confidence: likely; importance: 10
ratty  gwern  analysis  faq  ai  risk  speedometer  intelligence  futurism  cs  computation  complexity  tcs  linear-algebra  nonlinearity  convexity-curvature  average-case  adversarial  article  time-complexity  singularity  iteration-recursion  magnitude  multiplicative  lower-bounds  no-go  performance  hardware  humanity  psychology  cog-psych  psychometrics  iq  distribution  moments  complement-substitute  hanson  ems  enhancement  parable  detail-architecture  universalism-particularism  neuro  ai-control  environment  climate-change  threat-modeling  security  theory-practice  hacker  academia  realness  crypto  rigorous-crypto  usa  government 
april 2018 by nhaliday
Prisoner's dilemma - Wikipedia
caveat to result below:
An extension of the IPD is an evolutionary stochastic IPD, in which the relative abundance of particular strategies is allowed to change, with more successful strategies relatively increasing. This process may be accomplished by having less successful players imitate the more successful strategies, or by eliminating less successful players from the game, while multiplying the more successful ones. It has been shown that unfair ZD strategies are not evolutionarily stable. The key intuition is that an evolutionarily stable strategy must not only be able to invade another population (which extortionary ZD strategies can do) but must also perform well against other players of the same type (which extortionary ZD players do poorly, because they reduce each other's surplus).[14]

Theory and simulations confirm that beyond a critical population size, ZD extortion loses out in evolutionary competition against more cooperative strategies, and as a result, the average payoff in the population increases when the population is bigger. In addition, there are some cases in which extortioners may even catalyze cooperation by helping to break out of a face-off between uniform defectors and win–stay, lose–switch agents.[8]

https://alfanl.com/2018/04/12/defection/
Nature boils down to a few simple concepts.

Haters will point out that I oversimplify. The haters are wrong. I am good at saying a lot with few words. Nature indeed boils down to a few simple concepts.

In life, you can either cooperate or defect.

Used to be that defection was the dominant strategy, say in the time when the Roman empire started to crumble. Everybody complained about everybody and in the end nothing got done. Then came Jesus, who told people to be loving and cooperative, and boom: 1800 years later we get the industrial revolution.

Because of Jesus we now find ourselves in a situation where cooperation is the dominant strategy. A normie engages in a ton of cooperation: with the tax collector who wants more and more of his money, with schools who want more and more of his kid’s time, with media who wants him to repeat more and more party lines, with the Zeitgeist of the Collective Spirit of the People’s Progress Towards a New Utopia. Essentially, our normie is cooperating himself into a crumbling Western empire.

Turns out that if everyone blindly cooperates, parasites sprout up like weeds until defection once again becomes the standard.

The point of a post-Christian religion is to once again create conditions for the kind of cooperation that led to the industrial revolution. This necessitates throwing out undead Christianity: you do not blindly cooperate. You cooperate with people that cooperate with you, you defect on people that defect on you. Christianity mixed with Darwinism. God and Gnon meet.

This also means we re-establish spiritual hierarchy, which, like regular hierarchy, is a prerequisite for cooperation. It is this hierarchical cooperation that turns a household into a force to be reckoned with, that allows a group of men to unite as a front against their enemies, that allows a tribe to conquer the world. Remember: Scientology bullied the Cathedral’s tax department into submission.

With a functioning hierarchy, men still gossip, lie and scheme, but they will do so in whispers behind closed doors. In your face they cooperate and contribute to the group’s wellbeing because incentives are thus that contributing to group wellbeing heightens status.

Without a functioning hierarchy, men gossip, lie and scheme, but they do so in your face, and they tell you that you are positively deluded for accusing them of gossiping, lying and scheming. Seeds will not sprout in such ground.

Spiritual dominance is established in the same way any sort of dominance is established: fought for, taken. But the fight is ritualistic. You can’t force spiritual dominance if no one listens, or if you are silenced the ritual is not allowed to happen.

If one of our priests is forbidden from establishing spiritual dominance, that is a sure sign an enemy priest is in better control and has vested interest in preventing you from establishing spiritual dominance..

They defect on you, you defect on them. Let them suffer the consequences of enemy priesthood, among others characterized by the annoying tendency that very little is said with very many words.

https://contingentnotarbitrary.com/2018/04/14/rederiving-christianity/
To recap, we started with a secular definition of Logos and noted that its telos is existence. Given human nature, game theory and the power of cooperation, the highest expression of that telos is freely chosen universal love, tempered by constant vigilance against defection while maintaining compassion for the defectors and forgiving those who repent. In addition, we must know the telos in order to fulfill it.

In Christian terms, looks like we got over half of the Ten Commandments (know Logos for the First, don’t defect or tempt yourself to defect for the rest), the importance of free will, the indestructibility of evil (group cooperation vs individual defection), loving the sinner and hating the sin (with defection as the sin), forgiveness (with conditions), and love and compassion toward all, assuming only secular knowledge and that it’s good to exist.

Iterated Prisoner's Dilemma is an Ultimatum Game: http://infoproc.blogspot.com/2012/07/iterated-prisoners-dilemma-is-ultimatum.html
The history of IPD shows that bounded cognition prevented the dominant strategies from being discovered for over over 60 years, despite significant attention from game theorists, computer scientists, economists, evolutionary biologists, etc. Press and Dyson have shown that IPD is effectively an ultimatum game, which is very different from the Tit for Tat stories told by generations of people who worked on IPD (Axelrod, Dawkins, etc., etc.).

...

For evolutionary biologists: Dyson clearly thinks this result has implications for multilevel (group vs individual selection):
... Cooperation loses and defection wins. The ZD strategies confirm this conclusion and make it sharper. ... The system evolved to give cooperative tribes an advantage over non-cooperative tribes, using punishment to give cooperation an evolutionary advantage within the tribe. This double selection of tribes and individuals goes way beyond the Prisoners' Dilemma model.

implications for fractionalized Europe vis-a-vis unified China?

and more broadly does this just imply we're doomed in the long run RE: cooperation, morality, the "good society", so on...? war and group-selection is the only way to get a non-crab bucket civilization?

Iterated Prisoner’s Dilemma contains strategies that dominate any evolutionary opponent:
http://www.pnas.org/content/109/26/10409.full
http://www.pnas.org/content/109/26/10409.full.pdf
https://www.edge.org/conversation/william_h_press-freeman_dyson-on-iterated-prisoners-dilemma-contains-strategies-that

https://en.wikipedia.org/wiki/Ultimatum_game

analogy for ultimatum game: the state gives the demos a bargain take-it-or-leave-it, and...if the demos refuses...violence?

The nature of human altruism: http://sci-hub.tw/https://www.nature.com/articles/nature02043
- Ernst Fehr & Urs Fischbacher

Some of the most fundamental questions concerning our evolutionary origins, our social relations, and the organization of society are centred around issues of altruism and selfishness. Experimental evidence indicates that human altruism is a powerful force and is unique in the animal world. However, there is much individual heterogeneity and the interaction between altruists and selfish individuals is vital to human cooperation. Depending on the environment, a minority of altruists can force a majority of selfish individuals to cooperate or, conversely, a few egoists can induce a large number of altruists to defect. Current gene-based evolutionary theories cannot explain important patterns of human altruism, pointing towards the importance of both theories of cultural evolution as well as gene–culture co-evolution.

...

Why are humans so unusual among animals in this respect? We propose that quantitatively, and probably even qualitatively, unique patterns of human altruism provide the answer to this question. Human altruism goes far beyond that which has been observed in the animal world. Among animals, fitness-reducing acts that confer fitness benefits on other individuals are largely restricted to kin groups; despite several decades of research, evidence for reciprocal altruism in pair-wise repeated encounters4,5 remains scarce6–8. Likewise, there is little evidence so far that individual reputation building affects cooperation in animals, which contrasts strongly with what we find in humans. If we randomly pick two human strangers from a modern society and give them the chance to engage in repeated anonymous exchanges in a laboratory experiment, there is a high probability that reciprocally altruistic behaviour will emerge spontaneously9,10.

However, human altruism extends far beyond reciprocal altruism and reputation-based cooperation, taking the form of strong reciprocity11,12. Strong reciprocity is a combination of altruistic rewarding, which is a predisposition to reward others for cooperative, norm-abiding behaviours, and altruistic punishment, which is a propensity to impose sanctions on others for norm violations. Strong reciprocators bear the cost of rewarding or punishing even if they gain no individual economic benefit whatsoever from their acts. In contrast, reciprocal altruists, as they have been defined in the biological literature4,5, reward and punish only if this is in their long-term self-interest. Strong reciprocity thus constitutes a powerful incentive for cooperation even in non-repeated interactions and when reputation gains are absent, because strong reciprocators will reward those who cooperate and punish those who defect.

...

We will show that the interaction between selfish and strongly reciprocal … [more]
concept  conceptual-vocab  wiki  reference  article  models  GT-101  game-theory  anthropology  cultural-dynamics  trust  cooperate-defect  coordination  iteration-recursion  sequential  axelrod  discrete  smoothness  evolution  evopsych  EGT  economics  behavioral-econ  sociology  new-religion  deep-materialism  volo-avolo  characterization  hsu  scitariat  altruism  justice  group-selection  decision-making  tribalism  organizing  hari-seldon  theory-practice  applicability-prereqs  bio  finiteness  multi  history  science  social-science  decision-theory  commentary  study  summary  giants  the-trenches  zero-positive-sum  🔬  bounded-cognition  info-dynamics  org:edge  explanation  exposition  org:nat  eden  retention  long-short-run  darwinian  markov  equilibrium  linear-algebra  nitty-gritty  competition  war  explanans  n-factor  europe  the-great-west-whale  occident  china  asia  sinosphere  orient  decentralized  markets  market-failure  cohesion  metabuch  stylized-facts  interdisciplinary  physics  pdf  pessimism  time  insight  the-basilisk  noblesse-oblige  the-watchers  ideas  l 
march 2018 by nhaliday
Broadcasting — NumPy v1.13 Manual
When operating on two arrays, NumPy compares their shapes element-wise. It starts with the trailing dimensions, and works its way forward. Two dimensions are compatible when

they are equal, or
one of them is 1
If these conditions are not met, a ValueError: frames are not aligned exception is thrown, indicating that the arrays have incompatible shapes. The size of the resulting array is the maximum size along each dimension of the input arrays.

Arrays do not need to have the same number of dimensions. For example, if you have a 256x256x3 array of RGB values, and you want to scale each color in the image by a different value, you can multiply the image by a one-dimensional array with 3 values.
python  libraries  programming  howto  numerics  pls  linear-algebra  sci-comp  protocol-metadata  frameworks 
august 2017 by nhaliday
In the first place | West Hunter
We hear a lot about innovative educational approaches, and since these silly people have been at this for a long time now, we hear just as often about the innovative approaches that some idiot started up a few years ago and are now crashing in flames.  We’re in steady-state.

I’m wondering if it isn’t time to try something archaic.  In particular, mnemonic techniques, such as the method of loci.  As far as I know, nobody has actually tried integrating the more sophisticated mnemonic techniques into a curriculum.  Sure, we all know useful acronyms, like the one for resistor color codes, but I’ve not heard of anyone teaching kids how to build a memory palace.

https://westhunt.wordpress.com/2013/12/28/in-the-first-place/#comment-20106
I have never used formal mnemonic techniques, but life has recently tested me on how well I remember material from my college days. Turns out that I can still do the sorts of math and physics problems that I could then, in subjects like classical mechanics, real analysis, combinatorics, complex variables, quantum mechanics, statistical mechanics, etc. I usually have to crack the book though. Some of that material I have used from time to time, or even fairly often (especially linear algebra), most not. I’m sure I’m slower than I was then, at least on the stuff I haven’t used.

https://westhunt.wordpress.com/2013/12/28/in-the-first-place/#comment-20109
Long-term memory capacity must be finite, but I know of no evidence that anyone has ever run out of it. As for the idea that you don’t really need a lot of facts in your head to come up with new ideas: pretty much the opposite of the truth, in a lot of fields.

https://en.wikipedia.org/wiki/Method_of_loci

Mental Imagery > Ancient Imagery Mnemonics: https://plato.stanford.edu/entries/mental-imagery/ancient-imagery-mnemonics.html
In the Middle Ages and the Renaissance, very elaborate versions of the method evolved, using specially learned imaginary spaces (Memory Theaters or Palaces), and complex systems of predetermined symbolic images, often imbued with occult or spiritual significances. However, modern experimental research has shown that even a simple and easily learned form of the method of loci can be highly effective (Ross & Lawrence, 1968; Maguire et al., 2003), as are several other imagery based mnemonic techniques (see section 4.2 of the main entry).

The advantages of organizing knowledge in terms of country and place: http://marginalrevolution.com/marginalrevolution/2018/02/advantages-organizing-knowledge-terms-country-place.html

https://www.quora.com/What-are-the-best-books-on-Memory-Palace

fascinating aside:
US vs Nazi army, Vietnam, the draft: https://westhunt.wordpress.com/2013/12/28/in-the-first-place/#comment-20136
You think I know more about this than a retired major general and former head of the War College? I do, of course, but that fact itself should worry you.

He’s not all wrong, but a lot of what he says is wrong. For example, the Germany Army was a conscript army, so conscription itself can’t explain why the Krauts were about 25% more effective than the average American unit. Nor is it true that the draft in WWII was corrupt.

The US had a different mix of armed forces – more air forces and a much larger Navy than Germany. Those services have higher technical requirements and sucked up a lot of the smarter guys. That was just a product of the strategic situation.

The Germans had better officers, partly because of better training and doctrine, partly the fruit of a different attitude towards the army. The US, much of the time, thought of the Army as a career for losers, but Germans did not.

The Germans had an enormous amount of relevant combat experience, much more than anyone in the US. Spend a year or two on the Eastern Front and you learn.

And the Germans had better infantry weapons.

The US tooth-to-tail ratio was , I think, worse than that of the Germans: some of that was a natural consequence of being an expeditionary force, but some was just a mistake. You want supply sergeants to be literate, but it is probably true that we put too many of the smarter guys into non-combat positions. That changed some when we ran into manpower shortages in late 1944 and combed out the support positions.

This guy is back-projecting Vietnam problems into WWII – he’s mostly wrong.

more (more of a focus on US Marines than Army): https://www.quora.com/Were-US-Marines-tougher-than-elite-German-troops-in-WW2/answer/Joseph-Scott-13
west-hunter  scitariat  speculation  ideas  proposal  education  learning  retention  neurons  the-classics  nitty-gritty  visuo  spatial  psych-architecture  multi  poast  history  mostly-modern  world-war  war  military  strategy  usa  europe  germanic  cold-war  visual-understanding  cartoons  narrative  wordlessness  comparison  asia  developing-world  knowledge  metabuch  econotariat  marginal-rev  discussion  world  thinking  government  local-global  humility  wire-guided  policy  iron-age  mediterranean  wiki  reference  checklists  exocortex  early-modern  org:edu  philosophy  enlightenment-renaissance-restoration-reformation  qra  q-n-a  books  recommendations  list  links  ability-competence  leadership  elite  higher-ed  math  physics  linear-algebra  cost-benefit  prioritizing  defense  martial  war-nerd 
may 2017 by nhaliday
More on Multivariate Gaussians
Fact #1: mean and covariance uniquely determine distribution
Fact #3: closure under sum, marginalizing, and conditioning
covariance of conditional distribution is given by a Schur complement (independent of x_B. is that obvious?)
pdf  exposition  lecture-notes  stanford  nibble  distribution  acm  machine-learning  probability  levers  calculation  ground-up  characterization  rigidity  closure  nitty-gritty  linear-algebra  properties 
february 2017 by nhaliday
6.896: Essential Coding Theory
- probabilistic method and Chernoff bound for Shannon coding
- probabilistic method for asymptotically good Hamming codes (Gilbert coding)
- sparsity used for LDPC codes
mit  course  yoga  tcs  complexity  coding-theory  math.AG  fields  polynomials  pigeonhole-markov  linear-algebra  probabilistic-method  lecture-notes  bits  sparsity  concentration-of-measure  linear-programming  linearity  expanders  hamming  pseudorandomness  crypto  rigorous-crypto  communication-complexity  no-go  madhu-sudan  shannon  unit  p:**  quixotic  advanced 
february 2017 by nhaliday
What is the relationship between information theory and Coding theory? - Quora
basically:
- finite vs. asymptotic
- combinatorial vs. probabilistic (lotsa overlap their)
- worst-case (Hamming) vs. distributional (Shannon)

Information and coding theory most often appear together in the subject of error correction over noisy channels. Historically, they were born at almost exactly the same time - both Richard Hamming and Claude Shannon were working at Bell Labs when this happened. Information theory tends to heavily use tools from probability theory (together with an "asymptotic" way of thinking about the world), while traditional "algebraic" coding theory tends to employ mathematics that are much more finite sequence length/combinatorial in nature, including linear algebra over Galois Fields. The emergence in the late 90s and first decade of 2000 of codes over graphs blurred this distinction though, as code classes such as low density parity check codes employ both asymptotic analysis and random code selection techniques which have counterparts in information theory.

They do not subsume each other. Information theory touches on many other aspects that coding theory does not, and vice-versa. Information theory also touches on compression (lossy & lossless), statistics (e.g. large deviations), modeling (e.g. Minimum Description Length). Coding theory pays a lot of attention to sphere packing and coverings for finite length sequences - information theory addresses these problems (channel & lossy source coding) only in an asymptotic/approximate sense.
q-n-a  qra  math  acm  tcs  information-theory  coding-theory  big-picture  comparison  confusion  explanation  linear-algebra  polynomials  limits  finiteness  math.CO  hi-order-bits  synthesis  probability  bits  hamming  shannon  intricacy  nibble  s:null  signal-noise 
february 2017 by nhaliday
Carathéodory's theorem (convex hull) - Wikipedia
- any convex combination in R^d can be pared down to at most d+1 points
- eg, in R^2 you can always fit a point in convex hull in a triangle
tcs  acm  math.MG  geometry  levers  wiki  reference  optimization  linear-programming  math  linear-algebra  nibble  spatial  curvature  convexity-curvature 
january 2017 by nhaliday
Shtetl-Optimized » Blog Archive » Why I Am Not An Integrated Information Theorist (or, The Unconscious Expander)
In my opinion, how to construct a theory that tells us which physical systems are conscious and which aren’t—giving answers that agree with “common sense” whenever the latter renders a verdict—is one of the deepest, most fascinating problems in all of science. Since I don’t know a standard name for the problem, I hereby call it the Pretty-Hard Problem of Consciousness. Unlike with the Hard Hard Problem, I don’t know of any philosophical reason why the Pretty-Hard Problem should be inherently unsolvable; but on the other hand, humans seem nowhere close to solving it (if we had solved it, then we could reduce the abortion, animal rights, and strong AI debates to “gentlemen, let us calculate!”).

Now, I regard IIT as a serious, honorable attempt to grapple with the Pretty-Hard Problem of Consciousness: something concrete enough to move the discussion forward. But I also regard IIT as a failed attempt on the problem. And I wish people would recognize its failure, learn from it, and move on.

In my view, IIT fails to solve the Pretty-Hard Problem because it unavoidably predicts vast amounts of consciousness in physical systems that no sane person would regard as particularly “conscious” at all: indeed, systems that do nothing but apply a low-density parity-check code, or other simple transformations of their input data. Moreover, IIT predicts not merely that these systems are “slightly” conscious (which would be fine), but that they can be unboundedly more conscious than humans are.

To justify that claim, I first need to define Φ. Strikingly, despite the large literature about Φ, I had a hard time finding a clear mathematical definition of it—one that not only listed formulas but fully defined the structures that the formulas were talking about. Complicating matters further, there are several competing definitions of Φ in the literature, including ΦDM (discrete memoryless), ΦE (empirical), and ΦAR (autoregressive), which apply in different contexts (e.g., some take time evolution into account and others don’t). Nevertheless, I think I can define Φ in a way that will make sense to theoretical computer scientists. And crucially, the broad point I want to make about Φ won’t depend much on the details of its formalization anyway.

We consider a discrete system in a state x=(x1,…,xn)∈Sn, where S is a finite alphabet (the simplest case is S={0,1}). We imagine that the system evolves via an “updating function” f:Sn→Sn. Then the question that interests us is whether the xi‘s can be partitioned into two sets A and B, of roughly comparable size, such that the updates to the variables in A don’t depend very much on the variables in B and vice versa. If such a partition exists, then we say that the computation of f does not involve “global integration of information,” which on Tononi’s theory is a defining aspect of consciousness.
aaronson  tcstariat  philosophy  dennett  interdisciplinary  critique  nibble  org:bleg  within-without  the-self  neuro  psychology  cog-psych  metrics  nitty-gritty  composition-decomposition  complex-systems  cybernetics  bits  information-theory  entropy-like  forms-instances  empirical  walls  arrows  math.DS  structure  causation  quantitative-qualitative  number  extrema  optimization  abstraction  explanation  summary  degrees-of-freedom  whole-partial-many  network-structure  systematic-ad-hoc  tcs  complexity  hardness  no-go  computation  measurement  intricacy  examples  counterexample  coding-theory  linear-algebra  fields  graphs  graph-theory  expanders  math  math.CO  properties  local-global  intuition  error  definition  coupling-cohesion 
january 2017 by nhaliday
soft question - Why does Fourier analysis of Boolean functions "work"? - Theoretical Computer Science Stack Exchange
Here is my point of view, which I learned from Guy Kindler, though someone more experienced can probably give a better answer: Consider the linear space of functions f: {0,1}^n -> R and consider a linear operator of the form σ_w (for w in {0,1}^n), that maps a function f(x) as above to the function f(x+w). In many of the questions of TCS, there is an underlying need to analyze the effects that such operators have on certain functions.

Now, the point is that the Fourier basis is the basis that diagonalizes all those operators at the same time, which makes the analysis of those operators much simpler. More generally, the Fourier basis diagonalizes the convolution operator, which also underlies many of those questions. Thus, Fourier analysis is likely to be effective whenever one needs to analyze those operators.
q-n-a  math  tcs  synthesis  boolean-analysis  fourier  👳  tidbits  motivation  intuition  linear-algebra  overflow  hi-order-bits  insight  curiosity  ground-up  arrows  nibble  s:*  elegance  guessing 
december 2016 by nhaliday
gt.geometric topology - Intuitive crutches for higher dimensional thinking - MathOverflow
Terry Tao:
I can't help you much with high-dimensional topology - it's not my field, and I've not picked up the various tricks topologists use to get a grip on the subject - but when dealing with the geometry of high-dimensional (or infinite-dimensional) vector spaces such as R^n, there are plenty of ways to conceptualise these spaces that do not require visualising more than three dimensions directly.

For instance, one can view a high-dimensional vector space as a state space for a system with many degrees of freedom. A megapixel image, for instance, is a point in a million-dimensional vector space; by varying the image, one can explore the space, and various subsets of this space correspond to various classes of images.

One can similarly interpret sound waves, a box of gases, an ecosystem, a voting population, a stream of digital data, trials of random variables, the results of a statistical survey, a probabilistic strategy in a two-player game, and many other concrete objects as states in a high-dimensional vector space, and various basic concepts such as convexity, distance, linearity, change of variables, orthogonality, or inner product can have very natural meanings in some of these models (though not in all).

It can take a bit of both theory and practice to merge one's intuition for these things with one's spatial intuition for vectors and vector spaces, but it can be done eventually (much as after one has enough exposure to measure theory, one can start merging one's intuition regarding cardinality, mass, length, volume, probability, cost, charge, and any number of other "real-life" measures).

For instance, the fact that most of the mass of a unit ball in high dimensions lurks near the boundary of the ball can be interpreted as a manifestation of the law of large numbers, using the interpretation of a high-dimensional vector space as the state space for a large number of trials of a random variable.

More generally, many facts about low-dimensional projections or slices of high-dimensional objects can be viewed from a probabilistic, statistical, or signal processing perspective.

Scott Aaronson:
Here are some of the crutches I've relied on. (Admittedly, my crutches are probably much more useful for theoretical computer science, combinatorics, and probability than they are for geometry, topology, or physics. On a related note, I personally have a much easier time thinking about R^n than about, say, R^4 or R^5!)

1. If you're trying to visualize some 4D phenomenon P, first think of a related 3D phenomenon P', and then imagine yourself as a 2D being who's trying to visualize P'. The advantage is that, unlike with the 4D vs. 3D case, you yourself can easily switch between the 3D and 2D perspectives, and can therefore get a sense of exactly what information is being lost when you drop a dimension. (You could call this the "Flatland trick," after the most famous literary work to rely on it.)
2. As someone else mentioned, discretize! Instead of thinking about R^n, think about the Boolean hypercube {0,1}^n, which is finite and usually easier to get intuition about. (When working on problems, I often find myself drawing {0,1}^4 on a sheet of paper by drawing two copies of {0,1}^3 and then connecting the corresponding vertices.)
3. Instead of thinking about a subset S⊆R^n, think about its characteristic function f:R^n→{0,1}. I don't know why that trivial perspective switch makes such a big difference, but it does ... maybe because it shifts your attention to the process of computing f, and makes you forget about the hopeless task of visualizing S!
4. One of the central facts about R^n is that, while it has "room" for only n orthogonal vectors, it has room for exp⁡(n) almost-orthogonal vectors. Internalize that one fact, and so many other properties of R^n (for example, that the n-sphere resembles a "ball with spikes sticking out," as someone mentioned before) will suddenly seem non-mysterious. In turn, one way to internalize the fact that R^n has so many almost-orthogonal vectors is to internalize Shannon's theorem that there exist good error-correcting codes.
5. To get a feel for some high-dimensional object, ask questions about the behavior of a process that takes place on that object. For example: if I drop a ball here, which local minimum will it settle into? How long does this random walk on {0,1}^n take to mix?

Gil Kalai:
This is a slightly different point, but Vitali Milman, who works in high-dimensional convexity, likes to draw high-dimensional convex bodies in a non-convex way. This is to convey the point that if you take the convex hull of a few points on the unit sphere of R^n, then for large n very little of the measure of the convex body is anywhere near the corners, so in a certain sense the body is a bit like a small sphere with long thin "spikes".
q-n-a  intuition  math  visual-understanding  list  discussion  thurston  tidbits  aaronson  tcs  geometry  problem-solving  yoga  👳  big-list  metabuch  tcstariat  gowers  mathtariat  acm  overflow  soft-question  levers  dimensionality  hi-order-bits  insight  synthesis  thinking  models  cartoons  coding-theory  information-theory  probability  concentration-of-measure  magnitude  linear-algebra  boolean-analysis  analogy  arrows  lifts-projections  measure  markov  sampling  shannon  conceptual-vocab  nibble  degrees-of-freedom  worrydream  neurons  retrofit  oscillation  paradox  novelty  tricki  concrete  high-dimension  s:***  manifolds  direction  curvature  convexity-curvature  elegance  guessing 
december 2016 by nhaliday
Quarter-Turns | The n-Category Café
In other words, call an operator T a quarter-turn if ⟨Tx,x⟩=0 for all x. Then the real quarter-turns correspond to the skew symmetric matrices — but apart from the zero operator, there are no complex quarter turns at all.
tidbits  math  linear-algebra  hmm  mathtariat  characterization  atoms  inner-product  arrows  org:bleg  nibble 
december 2016 by nhaliday
« earlier      
per page:    204080120160

bundles : academeframemath

related tags

aaronson  ability-competence  abstraction  academia  accretion  accuracy  acm  acmtariat  additive  advanced  adversarial  advice  agriculture  ai  ai-control  alg-combo  algebra  algebraic-complexity  algorithms  alignment  altruism  amortization-potential  analogy  analysis  analytical-holistic  announcement  anthropology  antiquity  aphorism  apollonian-dionysian  applicability-prereqs  applications  approximation  arrows  article  ascetic  asia  atoms  audio  average-case  axelrod  backup  bare-hands  bayesian  behavioral-econ  ben-recht  benchmarks  berkeley  best-practices  better-explained  big-list  big-picture  big-surf  binomial  bio  bits  boltzmann  books  boolean-analysis  bounded-cognition  broad-econ  business  c(pp)  calculation  carmack  cartoons  CAS  causation  characterization  charity  chart  cheatsheet  checking  checklists  chemistry  chicago  china  christianity  circuits  classic  classification  clever-rats  climate-change  closure  coarse-fine  code-dive  coding-theory  cog-psych  cohesion  cold-war  combo-optimization  comics  commentary  common-case  communication-complexity  comparison  competition  complement-substitute  complex-systems  complexity  composition-decomposition  compressed-sensing  compression  computation  concentration-of-measure  concept  conceptual-vocab  concrete  confluence  confusion  conquest-empire  context  convergence  convexity-curvature  cooperate-defect  coordination  core-rats  correlation  cost-benefit  counterexample  coupling-cohesion  course  creative  criminal-justice  critique  crosstab  crypto  cs  cultural-dynamics  curiosity  curvature  cybernetics  darwinian  data-science  data-structures  dataviz  dbs  debate  debugging  decentralized  decision-making  decision-theory  deep-learning  deep-materialism  defense  definition  degrees-of-freedom  dennett  density  descriptive  detail-architecture  developing-world  devops  devtools  differential  differential-privacy  dimensionality  direction  discrete  discussion  distribution  diversity  documentation  domestication  dotnet  DP  DSL  duality  dynamic  dynamical  early-modern  ecology  economics  econotariat  ecosystem  eden  editors  education  EEA  egalitarianism-hierarchy  EGT  electromag  elegance  elite  embedded  embedding  embeddings  emotion  empirical  ems  ends-means  engineering  enhancement  enlightenment-renaissance-restoration-reformation  entropy-like  environment  envy  equilibrium  ergodic  error  estimate  ethics  europe  evolution  evopsych  examples  existence  exocortex  expanders  expectancy  expert  expert-experience  explanans  explanation  exploratory  exposition  extrema  facebook  faq  farmers-and-foragers  features  fields  finance  finiteness  flexibility  formal-methods  formal-values  forms-instances  fourier  frameworks  free-riding  frontend  frontier  functional  futurism  game-theory  gedanken  generalization  generative  geometry  georgia  germanic  giants  git  gnon  gnosis-logos  golang  government  gowers  gradient-descent  graph-theory  graphical-models  graphs  greedy  ground-up  group-selection  growth  GT-101  guessing  guide  guilt-shame  gwern  hacker  hamming  hanson  hardness  hardware  hari-seldon  hashing  haskell  heavyweights  henrich  heuristic  hg  hi-order-bits  hierarchy  high-dimension  high-variance  higher-ed  history  hmm  hn  homogeneity  honor  howto  hsu  human-capital  humanity  humility  hypothesis-testing  ideas  identity  ideology  IEEE  iidness  illusion  impact  impro  incentives  individualism-collectivism  industrial-revolution  info-dynamics  info-foraging  information-theory  init  inner-product  insight  intelligence  interdisciplinary  interests  intersection-connectedness  intricacy  intuition  invariance  investing  iq  iron-age  isotropy  iteration-recursion  iterative-methods  javascript  justice  jvm  kernels  knowledge  language  large-factor  latent-variables  leadership  learning  learning-theory  lecture-notes  lectures  lens  lesswrong  let-me-see  letters  levers  leviathan  libraries  lifts-projections  limits  linear-algebra  linear-models  linear-programming  linearity  liner-notes  links  lisp  list  local-global  logic  lol  long-short-run  love-hate  lower-bounds  luca-trevisan  machine-learning  macro  madhu-sudan  magnitude  manifolds  marginal-rev  market-failure  marketing  markets  markov  martial  martingale  matching  math  math.AC  math.AG  math.CA  math.CO  math.CT  math.DS  math.FA  math.GN  math.GR  math.MG  math.NT  math.RT  mathtariat  matrix-factorization  measure  measurement  medieval  mediterranean  meta:math  meta:rhetoric  metabuch  metameta  methodology  metric-space  metrics  michael-jordan  michael-nielsen  micro  mihai  military  mit  mixing  model-class  models  moments  monotonicity  monte-carlo  mostly-modern  motivation  mrtz  multi  multiplicative  music-theory  n-factor  narrative  network-structure  networking  neuro  neurons  new-religion  news  nibble  nietzschean  nitty-gritty  nlp  no-go  noblesse-oblige  nonlinearity  norms  novelty  number  numerics  objektbuch  ocaml-sml  occident  off-convex  old-anglo  oly  online-learning  oop  open-problems  openai  operational  optimization  order-disorder  ORFE  org:bleg  org:edge  org:edu  org:inst  org:mag  org:mat  org:nat  org:popup  org:sci  organizing  orient  orourke  oscillation  oss  overflow  oxbridge  p:**  p:***  p:null  p:someday  p:whenever  PAC  papers  parable  paradox  parasites-microbiome  parsimony  patho-altruism  pdf  peace-violence  performance  perturbation  pessimism  phase-transition  philosophy  physics  pic  pigeonhole-markov  piracy  plots  pls  poast  poetry  policy  polynomials  population  positivity  pragmatic  pre-2013  preimage  presentation  princeton  prioritizing  probabilistic-method  probability  problem-solving  prof  programming  project  proofs  properties  proposal  protocol-metadata  prudence  pseudorandomness  psych-architecture  psychology  psychometrics  public-goodish  putnam-like  python  q-n-a  qra  quantitative-qualitative  quantum  questions  quixotic  quotes  r-lang  rand-approx  random  random-matrices  ranking  rationality  ratty  reading  realness  recommendations  recruiting  reduction  reference  reflection  regression  regularization  reinforcement  relativity  relaxation  religion  replication  reputation  research  retention  retrofit  review  rigidity  rigor  rigorous-crypto  risk  ritual  roadmap  robust  roots  rot  rounding  rust  s:*  s:**  s:***  s:null  sampling  sanjeev-arora  sapiens  scala  scale  scholar-pack  sci-comp  science  scitariat  SDP  search  sebastien-bubeck  security  selection  self-interest  sensitivity  separation  sequential  series  shannon  shift  short-circuit  signal-noise  signaling  signum  simplex  singularity  sinosphere  skeleton  slides  smoothness  social-norms  social-science  sociality  sociology  soft-question  software  span-cover  sparsity  spatial  spectral  speculation  speedometer  stackex  stanford  stat-mech  static-dynamic  stats  stochastic-processes  store  stories  strategy  street-fighting  structure  study  studying  stylized-facts  subculture  sublinear  success  summary  survey  syntax  synthesis  systematic-ad-hoc  systems  talks  tcs  tcstariat  teaching  tech  technical-writing  techtariat  telos-atelos  tensors  terminal  the-basilisk  the-classics  the-great-west-whale  the-self  the-trenches  the-watchers  theory-practice  theos  thermo  thick-thin  thinking  threat-modeling  thurston  tidbits  tightness  tim-roughgarden  time  time-complexity  time-series  toolkit  tools  top-n  topics  topology  track-record  tribalism  tricki  tricks  troll  trust  truth  tutorial  types  uniqueness  unit  universalism-particularism  unix  unsupervised  us-them  usa  valiant  values  vampire-squid  vcs  video  visual-understanding  visualization  visuo  volo-avolo  von-neumann  walls  war  war-nerd  web  west-hunter  westminster  whole-partial-many  wiki  wire-guided  within-without  wordlessness  world  world-war  wormholes  worrydream  worse-is-better/the-right-thing  writing  yak-shaving  yoga  zero-positive-sum  🎓  👳  🔬  🖥  🤖  🦉 

Copy this bookmark:



description:


tags: