Editing Basis (linear algebra) (section)

===Random basis===
For a [[probability distribution]] in {{math|'''R'''<sup>''n''</sup>}} with a [[probability density function]], such as the equidistribution in an ''n''-dimensional ball with respect to Lebesgue measure, it can be shown that {{mvar|n}} randomly and independently chosen vectors will form a basis [[with probability one]], which is due to the fact that {{mvar|n}} linearly dependent vectors {{math|'''x'''<sub>1</sub>}}, ..., {{math|'''x'''<sub>''n''</sub>}} in {{math|'''R'''<sup>''n''</sup>}} should satisfy the equation {{math|1=det['''x'''<sub>1</sub> ⋯ '''x'''<sub>''n''</sub>] = 0}} (zero determinant of the matrix with columns {{math|'''x'''<sub>''i''</sub>}}), and the set of zeros of a non-trivial polynomial has zero measure. This observation has led to techniques for approximating random bases.<ref>{{cite journal |first1=B. |last1=Igelnik |first2=Y.-H. |last2=Pao |title=Stochastic choice of basis functions in adaptive function approximation and the functional-link net |journal=IEEE Trans. Neural Netw. |volume=6 |issue=6 |year=1995 |pages=1320–1329 |doi=10.1109/72.471375 |pmid=18263425 }}</ref><ref name = "GorbanTyukin2016">{{cite journal
 | first1 = Alexander N. | last1 = Gorban | author1-link = Aleksandr Gorban
 | first2 = Ivan Y. | last2 = Tyukin | first3 = Danil V. | last3 = Prokhorov | first4 = Konstantin I. | last4 = Sofeikov
 | journal = [[Information Sciences (journal)|Information Sciences]]
 | title = Approximation with Random Bases: Pro et Contra
 | pages = 129–145
 | doi = 10.1016/j.ins.2015.09.021 | volume = 364-365 | year = 2016 | arxiv = 1506.04631 | s2cid = 2239376 }}</ref>

[[File:Random almost orthogonal sets.png|thumb|270px|Empirical distribution of lengths N of pairwise almost orthogonal chains of vectors that are independently randomly sampled from the ''n''-dimensional cube {{math|[−1, 1]<sup>''n''</sup>}} as a function of dimension, ''n''. Boxplots show the second and third quartiles of this data for each ''n'', red bars correspond to the medians, and blue stars indicate means. Red curve shows theoretical bound given by Eq. (1) and green curve shows a refined estimate.<ref name = "GorbanTyukin2016"/>]]

It is difficult to check numerically the linear dependence or exact orthogonality. Therefore, the notion of ε-orthogonality is used. For [[Inner product space|spaces with inner product]], ''x'' is ε-orthogonal to ''y'' if <math>\left|\left\langle x,y \right\rangle\right| / \left(\left\|x\right\|\left\|y\right\|\right) < \varepsilon</math> (that is, cosine of the angle between {{mvar|x}} and {{mvar|y}} is less than {{mvar|ε}}).

In high dimensions, two independent random vectors are with high probability almost orthogonal, and the number of independent random vectors, which all are with given high probability pairwise almost orthogonal, grows exponentially with dimension. More precisely, consider equidistribution in ''n''-dimensional ball. Choose ''N'' independent random vectors from a ball (they are [[Independent and identically distributed random variables|independent and identically distributed]]). Let ''θ'' be a small positive number. Then for
{{NumBlk||<math display="block">N\leq {\exp}\bigl(\tfrac14\varepsilon^2n\bigr)\sqrt{-\ln(1-\theta)}</math>|Eq. 1}}

{{mvar|N}} random vectors are all pairwise ε-orthogonal with probability {{math|1 − ''θ''}}.<ref name = "GorbanTyukin2016"/> This {{mvar|N}} growth exponentially with dimension {{mvar|n}} and <math>N\gg n</math> for sufficiently big {{mvar|n}}. This property of random bases is a manifestation of the so-called {{em|measure concentration phenomenon}}.<ref>{{cite journal |first=Shiri |last=Artstein |author-link=Shiri Artstein |title=Proportional concentration phenomena of the sphere |journal=[[Israel Journal of Mathematics]] |volume=132 |year=2002 |issue=1 |pages=337–358 |doi=10.1007/BF02784520 |doi-access=free|url=http://www.tau.ac.il/~shiri/israelj/ISRAJ.pdf |citeseerx=10.1.1.417.2375|s2cid=8095719}}</ref>

The figure (right) illustrates distribution of lengths N of pairwise almost orthogonal chains of vectors that are independently randomly sampled from the ''n''-dimensional cube {{math|[−1, 1]<sup>''n''</sup>}} as a function of dimension, ''n''. A point is first randomly selected in the cube. The second point is randomly chosen in the same cube. If the angle between the vectors was within {{math|π/2 ± 0.037π/2}} then the vector was retained. At the next step a new vector is generated in the same hypercube, and its angles with the previously generated vectors are evaluated. If these angles are within {{math|π/2 ± 0.037π/2}} then the vector is retained. The process is repeated until the chain of almost orthogonality breaks, and the number of such pairwise almost orthogonal vectors (length of the chain) is recorded. For each ''n'', 20 pairwise almost orthogonal chains were constructed numerically for each dimension. Distribution of the length of these chains is presented.