Level Set (ℝⁿ ⇨ ℝ)(Under Construction!)

Level Set(Contour Line)(Isoline)

「等高線」。函數曲線一樣高的地方。習慣畫成俯瞰平面圖。

連續可微函數的等高線,可以是一條封閉曲線、一條開放曲線、多條上述曲線。

甚至等高線粗細不一。

函數等於定值,形成方程式,即是等高線。

f(x,y)是一群等高線。f(x,y) = 0是一個等高線。f(x,y) ≥ 0是一群等高線,形成區域,區分內部外部。

等高線,無限微小、無限綿密、無限多,填滿整個空間。

一、函數:等高線彼此不相交。

二、連續:等高線沒有端點。等高線升高降低,宛如膨脹消泄。

三、可微:等高線沒有尖角。等高線每一點只有唯一一條切線。

極值位於兩個等高線的交集。注意到極值可能不只一個。

一、函數:兩個等高線,若等高、又最高,則交集是極值。

二、連續:兩個等高線,只會內接或外接,不會交叉。

三、可微:兩個等高線,交會之處,每一點只有唯一一條切線。

各式各樣的等高線

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

梯度:等高線的垂直方向。

稜線、谷線:若內高外低,等高線們一齊凸起之處是稜線、一齊凹陷之處是谷線。若內低外高,則相反。【查無定義】

高峻處、低窪處:各種尺寸的同心圓(甚至其他形狀)的極值,連成一線。【查無名稱】

容易計算的函數類型

Monotone Function:單調函數。遞增、遞減。

Convex Function:凸函數。斜率是單調函數,遞增是凸、遞減是凹。

Unimodal Function:單峰函數。先遞增(減)再遞減(增)。

Quasiconvex Function:擬凸函數。等高線是凸的,遞增是擬凸、遞減是擬凹。

https://mjo.osborne.economics.utoronto.ca/index.php/tutorial/index/1/qcc/t
f(a,x) = ax  在第一三象限是擬凹函數、第二四象限是擬凸函數
https://www.desmos.com/calculator/vkru83pare

[A,X] = meshgrid(-10:0.5:10,-10:10);
Z = A .* X;
surf(A,X,Z)

f(a,x) = (ax)^2 四個象限都是擬凹函數,合起來看像個碗(假的凸函數),截面是拋物線
https://www.desmos.com/calculator/roky6zr9lf

[A,X] = meshgrid(-10:0.5:10,-10:10);
Z = A .* X;
Z = Z .* Z;
surf(A,X,Z)

Level Set (ℝⁿ ⇨ ℝᵐ)(Under Construction!)

Level Set

多變量函數是箭矢圖。據我所知似乎沒有等高線的概念。

容易計算的多變量函數類型

遞增函數、凸函數、平緩函數都必須重新定義。

我找不到相關資料,事情相當棘手。以下的定義通通尚待確認。

Increasing Function ⮕ Positive Semidefinite Matrix

多變量函數的遞增函數,定義成一次微分是半正定矩陣。

單變量函數:斜率大於零(分子分母同號)
                           f(b) - f(a)
function f is monotone iff ――――――――――― ≥ 0
                              b - a

多變量函數:點積大於零(分子分母同號)(轉角介於±90˚)
multivariate function f is monotone iff (b - a) ∙ (f(b) - f(a)) ≥ 0

遞增數列,就是數字越來越大。遞增陣列,就是數字往右往下越大、往左往上越小。

遞增函數,就是數字越來越大。遞增二元函數,就是數字往右上的各種方向都越來越大。

輸入輸出推廣成向量,事情變得複雜:

一、採用輸出向量的長度來比大小。然而向量長度沒有負數,沒辦法越來越小,不存在嚴格遞減。這個方式不行。

二、改用輸入向量與輸出向量的點積來比大小。然而大小的意義整個扭曲了,轉角介於±90˚叫做變大,否則叫做變小。

單變量函數是遞增函數:處處斜率都是正數或零。
多變量函數是遞增函數:處處梯度都是半正定矩陣(特徵值都是正數或零)。
線性函數Ax是遞增函數:處處梯度都是Aᵀ,Aᵀ是半正定矩陣。

Increasing Function ⮕ Nonnegative Divergence

多變量函數的遞增函數,定義成散度大於等於零。

單變量函數:斜率大於零
function f is monotone iff ∂/∂x f(x) ≥ 0

多變量函數:散度大於零
multivariate function f is monotone iff [ ∂/∂x ] ∙ [ f(x) ] ≥ 0
                                        [ ∂/∂y ]   [ f(y) ]

一維箭矢圖有個特性:遞增函數(處處斜率大於零),箭矢自零散開。遞減函數(處處斜率小於零),箭矢聚集至零。

多維箭矢圖則是:處處散度大於零,箭矢自零散開。處處散度小於零,箭矢聚集至零。

散開的地方稱作源,聚集的地方稱作匯。當函數起起伏伏、而且很多地方是零,就有許多源匯。正負無限大的地方也是源匯。

儘管源匯很吸睛,然並卵。

Lipschitz Function ⮕ Johnson-Lindenstrauss Lemma

(1-δ) ‖x-y‖² ≤ ‖f(x)-f(y)‖² ≤ (1+δ) ‖x-y‖²

半正定矩陣:向量經過變換,角度差異在九十度以內。

JL矩陣:向量經過變換,長度平方差異在δ倍以內。

Lipschitz Function ⮕ Diagonally Dominant Matrix

多變量函數的平緩函數定義成對角優勢矩陣。

monotone: 0 ≤ (f(b) - f(a)) / (b - a)
Lipschitz: -1 ≤ (f(b) - f(a)) / (b - a) ≤ +1
positive Lipschitz => monotone
|f(a) + f(b)| ≤ |a + b|   其中一個變數變號
diagonally dominant matrix = 每個橫條都是Lipschitz function
(對於橫條的非主對角線元素來說。)
(例如Gauss–Seidel,更新x,方程式5x + y = 5是陡峭的,很近就撞到,所以收斂。
(更新式x = 1 - 0.2y,對y而言,斜率-1 ≤ -0.2 ≤ 1是平緩的。)
positive diagonally dominant => positive definite => monotone
https://books.google.com.tw/books?id=KVfSBwAAQBAJ&pg=PA105

Convex Function ⮕ Submodular Function

《Learning Submodular Functions》
Submodularity is in many ways similar to concavity of functions
defined on Rn. For example, concavity of differentiable functions
is equivalent to gradient monotonicity, and submodularity is equivalent
to monotonicity of the marginal values:

• Non-negative if f(S) ≥ 0 for all S.
• Monotone (or non-decreasing) if f(S) ≤ f(T) for all S ⊆ T.
• Submodular if f(A) + f(B) ≥ f(A ∪ B) + f(A ∩ B) ∀A,B ⊆ [n].
  or equivalently f(A ∪ {i}) − f(A) ≥ f(B ∪ {i}) − f(B)
  for all A ⊆ B ⊆ [n] and i ∉ B.
• Subadditive if f(S) + f(T) ≥ f(S ∪ T) for all S,T ⊆ [n].
• L-Lipschitz if |f(S + x) − f(S)| ≤ L for all S ⊆ [n] and x ∈ [n].

Mathematical Morphology

Mathematical Morphology

Histogram3D[{{0,0},{0,0},{0,0}},{1},Boxed->False,Axes->None]

【註:我製圖技術差,只好介紹陣列版本,而非函數版本。】

調整函數形狀的學問。因為不是顯學,所以名稱矯揉造作,不像一般的數學名詞那樣地簡潔有力。關鍵字grayscale morphology。

基本操作是dilation和erosion,進階操作由基本操作組成。

            dilation:鄰近格子取最大值。功效是補厚。
             erosion:鄰近格子取最小值。功效是削薄。
             closing:先 dilation 再 erosion。
             opening:先 erosion 再 dilation。
   top-hat transform:原函數減掉 opening。
bottom-hat transform:closing 減掉原函數。

鄰近格子可以自訂樣式。另外,大樣式多半可以改為小樣式,效果相同而且時間複雜度更低。

例如5×5,改為兩波3×3,亦得取得5×5範圍內的最小值(最大值)。本來讀取X×Y×5×5格,變成只讀取X×Y×3×3×2格。

運算不可逆、不可抵銷,沒有反運算。個人推測這些運算可以減少亂度。

額外使用過濾函數

進階版本。額外設計一個過濾函數。設計不同的過濾函數,得到不同的效果。

窮舉原函數的每個位置;針對一個位置,令過濾函數的中心對準該位置,各個位置點對點相加(相減)後,才取最大值(最小值)。

邏輯運算的版本

不知道為什麼,影像處理教科書非常喜歡討論邏輯運算的版本。數值改成false和true,最大值(最小值)改成OR(AND),功效是增厚(削薄)圖形的外緣。

UVa 12702