Son zamanlarda seyrek betimleme/kodlama konusunda çalışıyorum. Seyrek betimlemeden kasıt şu: İlgilendiğimizin vektörün büyük bir kısmı 0 olacak, yani yalnızca birkaç değeri 0'dan farklı olacak. Örneğin $\mathbf{A} \in \mathbb{R}^{m\times n}$ matrisi $m$ boyutunda $n$ tane sütun, vektöründen oluşsun ve her sütun veritabanındaki bir yüz resmini ifade etsin. Yani veri matrisinin sütunları örnekleri içersin. Amacımız da gözlemlediğimiz bir $y \in \mathbb{R}^{m \times 1}$ vektörünün hangi kişiye ait yüz olduğunu bulmak olsun. Doğrudan $y$'nin değerleri üstünde çalışmak yerine şöyle bir model yazıyoruz:

$$\mathbf{A}x = y$$

ve $x$'i bulmak için şöyle bir eniyilemeye gidiyoruz: $\operatorname{argmin} \|x\|_1$

Yani eşitlikten taviz vermemeye çalışarak $\sum_i |x_i|$ değerini mümkün olduğunca en küçüğe düşürmek istiyoruz.

Bu problemi çözdüğümüzde elde ettiğimiz $x$ değerindeki 0'dan farklı olan değerler (özellikle yüksek olanlar) o yüze sahip kişinin başka resimlerine ait sütunlara tekabül ediyor. Eğer sonuç seyrek çıkmazsa, yani böyle ayrışan değerler gözükmezse kişinin veritabanında olmadığını söyleyebiliyoruz. Konuyla ilgili detaylı bilgiye [1]'den bakabilirsiniz.

Bahsi geçen eniyileme problemini çözmek için içbükey eniyileme (convex optimization) / doğrusal programlama kullanmak gerekiyor. Maalesef bu konuda derin bilgi sahibi değilim. Fakat yazının başlığında adı geçen $l_1$-Magic araçkutusu buna benzer 7 adet $l_1$ eniyileme problemini çözmek için fonksiyonlar sunuyor. Araçkutusunu indirdiğinizde örnek kodlar ve iyi hazırlanmış bir dokümantasyon içerdiğini göreceksiniz.

[1] J. Wright, A.Y. Yang, A. Ganesh, S.S. Sastry, ve Y. Ma, “Robust face recognition via sparse representation.,” IEEE transactions on pattern analysis and machine intelligence, vol. 31, Mar. 2009, pp. 210-27.