التقريب منخفض الرتبة

الاحتفاظ بالجزء المهم من المصفوفة

تكتب SVD المصفوفة مجموعًا لطبقات من الرتبة واحد، $A=\sum_i\sigma_i\mathbf u_i\mathbf v_i^{T}$، مرتبة من الأكبر إلى الأصغر. والاحتفاظ بأول $k$ طبقة فقط يعطي $A_k=U_k\Sigma_kV_k^{T}$، وهي مصفوفة من الرتبة $k$. وتنص نظرية إيكارت-يونغ على أن هذا البتر هو أفضل تقريب من الرتبة $k$ على الإطلاق، سواء قيس الخطأ بنظيم فروبينيوس أو بالنظيم الطيفي. ولا يتفوق أي اختيار بارع لـ $k$ اتجاهًا على أعلى $k$ اتجاهًا مفردًا.

الخطأ هو بالضبط القيم المفردة المهملة، فنسبة الحجم المربع المحتفظ بها هي $\sum_{i\le k}\sigma_i^2\big/\sum_i\sigma_i^2$ وتسمى غالبًا التباين المفسَّر حين تكون $A$ بيانات مطروحًا منها المتوسط. وتحتاج مصفوفة $m\times n$ إلى $k(m+n+1)$ عددًا فقط بدل $mn$ في تقريب من الرتبة $k$، ولذلك فالرتبة المنخفضة ضغط أيضًا. وفي المالية تكون الطبقات ذات $\sigma_i$ الصغيرة ضجيج عينة في معظمها، فبترها تنقية، ويُختار $k$ بعتبة على النسبة المحتفظ بها أو بفجوة في القيم المفردة.

• إيكارت-يونغ: بتر SVD عند $k$ حدًّا هو أفضل تقريب من الرتبة $k$ في النظيمين.
• الخطأ: فروبينيوس $\sqrt{\sum_{i>k}\sigma_i^2}$ والطيفي $\sigma_{k+1}$.
• التخزين: $k(m+n+1)$ عددًا بدل $mn$.

المختبر: ما الذي يُقيَّم

• خطأ فروبينيوس15 نقطة
• النسبة المحتفظ بها15 نقطة
• تقريب من الرتبة واحد15 نقطة
• تخزين مصفوفة منخفضة الرتبة10 نقطة
• نظرية إيكارت-يونغ15 نقطة
• ضغط مصفوفة15 نقطة
• لماذا ينقّي البتر15 نقطة