다음은 쉬운 추정치입니다. 여기에는 콜 설정 S ⊆ X ε -net 메트릭 공간의 X를 모든 점 때 X ∈ X , 지점이 존재 들 ∈ S 간의 거리되도록 X 와 S를 이다 많아야 ε . 당신의 정의에 엄격한 불평등하려면 ε -net을, 당신은의 값을 조정할 수 ε을 약간.

그것은 || || _∞ ≤ || || _C ≤ n ² || || _∞ , 여기서 || || _∞ 는 n × n 행렬 A 의 엔트리 별 최대-노름을 나타냅니다 .

그것이 구성 쉽다 ε 메트릭 공간 -net를 ([0,1] ^N , D _∞ ) 크기 ⌈1 / (2 ε ) ⌉ ^N 하고,이 크기가 최소임을 표시하는 것은 어렵지 않다. (최소 성을 나타내려면 좌표가 1 / ⌈1 / (2 ε ) −1⌉의 배수 인 ⌈1 / (2 ε ) ⌉ ^N 점을 고려하고이 두 점 사이의 거리가 2보다 큼 ε .) N = n ² 로 설정 하고이를 컷 노름과 최대 노름 사이의 전술 한 비교와 결합함으로써 ε 의 최소 ​​카디널리티절단 규범에 대한 -net은 적어도 ⌈1 / (2 ε ) ⌉ ^{n 2} 이고 최대 ⌈ n ² / (2 ε ) ⌉ ^{n 2} 입니다.

업데이트 : 계산이 정확 하면 volume 인수 로 더 낮은 하한 Ω ( n / ε ) ^{n 2} 를 얻을 수 있습니다. 이렇게하려면 컷 규범과 관련하여 ε 볼 의 체적에 상한이 필요합니다 .

먼저 단일 벡터의 “절단 기준”을 고려합니다. 이는 양의 요소의 합과 음의 요소의 합의 최대 사이입니다. 볼륨 보여 어렵지 않다 ε ℝ에서 -ball는 ^N 이 “컷 표준”에 대해 동일하다

$$\varepsilon^n \sum_{I \subseteq \{1,\dotsc,n\}} \frac{1}{|I|!} \cdot \frac{1}{(n-|I|)!} = \varepsilon^n \sum_{r=0}^n \binom{n}{r} \frac{1}{r!(n-r)!}$$

$$= \frac{\varepsilon^n}{n!} \sum_{r=0}^n \binom{n}{r}^2 = \frac{\varepsilon^n}{n!} \binom{2n}{n} = \frac{(2n)!\varepsilon^n}{(n!)^3}.$$

다음으로, n × n 행렬 A 의 컷 노름이 각 행의 컷 노름보다 크거나 같기 때문에, ℝ ^{n × n} 에서 의 ε- 볼 의 부피는 최대 부피의 n 제곱이다. ε – 볼 ℝ에서 ^N . 따라서 [0,1] ^{n × n} 의 ε -net의 크기는 최소한

$$\frac{(n!)^{3n}}{(2n)!^n \varepsilon^{n^2}} = \left(\Omega\left(\frac{n}{\varepsilon}\right)\right)^{n^2},$$

여기서 마지막 평등은 Stirling의 공식 을 사용하는 지루한 계산입니다 : ln n ! = n ln n – n + O (log n ).

답변