Construction of approximately equiangular tight frames and their applicatios
Φόρτωση...
Ημερομηνία
Συγγραφείς
Τσιλιγιάννη, Ευαγγελία
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Frames are considered a natural extension of orthonormal bases to
overcomplete
span
ning systems. In the signal processing community, frames have mainly become popular
due to wavelets; however, many other frame families have been employed in numerous
applications, including source coding, robust transmission, code division multiple access
(CDMA) systems, and coding theory. The most important characteristic of frames is
redundancy, which adds more flexibility to signal expansions, facilitating various signal
processing tasks,
A finite frame with
N
vectors in an m-dimensional Hilbert space
is usually identi
fied with the
m
x
N
matrix
F
= [/ i
f 2
... /
at
],
ra <
N ,
with columns the frame vectors
f k
e Hm,
k
=
The most important properties of frames are
mutual coherence
and
spectral norm.
Mutual coherence is a measure of the maximal correlation between
the frame vectors and characterizes the degree of similarity between the columns of the
matrix
F.
Spectral norm measures how much a frame can dilate a unit norm coefficient
vector. Mutual coherence and spectral norm define particular classes of frames.
Unit
norm tight frames (UNTFs)
attain optimal bounds of spectral norm; these frames have
unit norm columns and orthogonal rows of equal norm. Unit norm tight frames with small
mutual coherence are referred to as
incoherent UNTFs.
The minimum possible mutual
coherence is attained by
equiangular tight frames (ETFs).
The frame vectors of ETFs
exhibit identical correlation and these frames are considered closest to orthonormal bases,
ETFs offer erasure-robust transmission in communications and minimize interuser
interference when employed as spreading sequences in multiuser communication systems.
Due to their incoherence, they are of interest in sparse representations and compressed
sensing. However, ETFs do not exist for all frame dimensions and their construction has
been proved extremely difficult.
This thesis presents two methods that produce real frames close to ETFs, The pro
posed constructions are motivated by specific applications, namely, compressed sensing
and sparse representations. Concerning sparse or compressible signals, that is, signals
with a few significant coefficients, compressed sensing and sparse representations have experienced a growing interest in the last decade, providing the ability of compact repre
sentations that serve various data sources. The mathematical model lying in the heart of
these applications involves an underdetermined linear system with more unknowns than
equations. Computing its sparsest solution, i.e,, the one with the fewest non-vanishing
coefficients is tractable with numerical methods. Standard numerical solvers include Or
thogonal Matching Pursuit (OMP) and Basis Pursuit (BP),
In sparse and redundant representations, we seek a sparse signal representation with
respect to a redundant
(overcomplete)
dictionary. Performance guarantees for the algo
rithms deployed to compute the non-vanishing coefficients require that the given dictio
nary forms an incoherent UNTF, While many incoherent dictionaries are known in the
literature, their limited sparsifving ability has promoted the design of learning based dic
tionaries, Often, learning based dictionaries do not satisfy the necessary properties for
numerical computations.
Compressed sensing is a sampling theory that allows signal reconstruction from an
incomplete number of measurements. Concerning signals that are sparse or compressible,
compressed sensing uses a sensing mechanism implemented by an appropriate matrix, the
so-called
projection matrix.
According to theoretical results, the projection matrix must
possess a property known as the restricted isometry property (RIP), Constructing RIP
matrices is difficult, as evaluation of RIP is
combinatorially
complex. Random Gaussian
or Bernoulli matrices satisfy RIP with high probability. Considering iV-dimensional sig
nals with
s
non-vanishing coefficients, recovery conditions for random matrices require
O(s logiV) measurements. More recent results formulate similar recovery guarantees for
projection matrices that form incoherent UNTFs, Thus, a new design strategy involves
the construction of projection matrices exhibiting small mutual coherence and spectral
norm.
Minimum bounds of mutual coherence and spectral norm are attained by ETFs; there
fore, the methods proposed here aim at the construction of frames as close to ETFs as
possible. The hrst method uses results from frame theory and relies on alternating pro
jection ideas. The produced constructions form UNTFs with remarkably small mutual
coherence, that is, incoherent UNTFs, The second method relies on recent results showing
that there is one-to-one correspondence of ETFs to a special type of graphs. The existence
of an ETF is determined by the so-called
signature matrix.
A signature matrix has the
form of the adjacency matrix of a graph and its spectrum consists of two distinct eigen
values, Viewing the construction of a signature matrix as an inverse eigenvalue problem,
we develop a numerical algorithm to compute a solution that approximates the signature
matrix of an ETF, The second method produces
nearly equiangular, nearly tight frames
,
that is, frames with similar column correlation and approximately optimal spectral norm.
The proposed frame constructions are employed as projection matrices in compressed
sensing, improving substantially the performance of the deployed algorithms in sparse
recovery. Considering that many signals are sparse or compressible under
overcomplete
dictionaries, incoherent UNTFs are also used for the design of optimized projection matrices with respect to a given representation dictionary. An additional way to employ the
proposed frames to solve underdetermined linear systems is the technique of precondition
ing, Applying preconditioning to sparse representations, we improve the performance of
the algorithms deployed to find the coefficients of the sparse signal. In compressed sens
ing, preconditioning is used to improve signal recovery when binary matrices are used as
projection matrices. Note that binary matrices are considered more suitable for hardware
implementation.
Besides compressed sensing and sparse representations, one of the proposed construc
tions has been employed in the design of near-optimal
codes
or
spreading sequences
in
synchronous CDMA systems. Optimal spreading sequences maximize the rate at which
the users can transmit and minimize interuser interference. Equal norm tight frames have
been proved optimal, if all users in the system are active. When the number of users
changes, the only frames that can minimize interuser interference are ETFs, However,
only a few ETF constructions are known in the literature. The near optimal codebook
presented here has the form of a nearly equiangular, nearly tight frame and minimizes
interuser interference even when some users in the system are silent.
Τα frames είναι υπερπλήρη συστήματα που παράγουν έναν διανυσματικό χώρο και θεωρούνται επέκταση των ορθοκανονικών βάσεων. Στην επεξεργασία σήματος, τα frames έγιναν γνωστά χάρη στα wavelets. Άλλοι τύποι frames έχουν χρησιμοποιηθεί σε ποικίλες εφαρμογές, όπως είναι η κωδικοποίηση, η εύρωστη μετάδοση και τα συστήματα πολλαπλής προσπέλασης με διαίρεση κώδικα (Code Division Multiple Aeeess-CDMA), Η υπερπληρό- τητα θεωρείται το πιο σημαντικό χαρακτηριστικό των frames, διότι προσφέρει ευελιξία στην αναπαράσταση ενός σήματος και διευκολύνει την επεξεργασία. Ένα frame με πεπερασμένο πλήθος διανυσμάτων που παράγει τον ///-διάστατο διανυ- σματικό χώρο Η™, συνήθως, αναπαριστάται από έναν πίνακα μεγέθους m x Ν , που έχει ως στήλες τα διανύσματα του frame, δηλαδή, F = [/ ι f 2 ... / at ], m < Ν , fk Ε Η™, k = Ι,.,.,Ν. Ως πιο σημαντικές ιδιότητες ενός frame θεωρούνται η αμοιβαία συνάφεια (mutual coherence) και η φασματική νόρμα (spectral norm). Η αμοιβαία συνάφεια αποτελεί ένα μέτρο της μέγιστης συσχέτισης των διανυσμάτων του frame και εκφράζει την ομοιότητα μεταξύ των στηλών του πίνακα F. Η φασματική νόρμα αποτελεί μέτρο της μέγιστης δυνατής διαστολής ενός μοναδιαίου διανύσματος, όταν αυτό πολλαπλασιαστεί με το frame. Οι δύο ιδιότητες ορίζουν συγκεκριμένες κατηγορίες frames. Τα unit norm tight frames (UNTFs) εμφανίζουν τη μικρότερη δυνατή φασματική νόρμα. Τα συγκεκριμένα frames έχουν στήλες μοναδιαίου μέτρου και ορθογώνιες γραμμές ίσου μέτρου. Όταν ένα UNTF εμφανίζει μικρή αμοιβαία συνάφεια, τότε χαρακτηρίζεται ως incoherent UNTF. Η ελάχιστη δυνατή αμοιβαία συνάφεια συναντάται στα equiangular tight frames (ETFs). Τα διανύσματα των ETFs εμφανίζουν ταυτόσημη συσχέτιση και τα frames αυτού του τύπου θεωρούνται ως η καλύτερη προσέγγιση ορθοκανονικών βάσεων. Τα ETFs έχουν προταθεί για την επίτευξη εύρωστης μετάδοσης σε συστήματα επικοινω νίας, καθώς και για την ελαχιστοποίηση της παρεμβολής μεταξύ των χρηστών σε συστήματα πολλαπλής προσπέλασης. Χάρη στην ελάχιστη αμοιβαία συνάφεια που εμφανίζουν, παρου σιάζουν ενδιαφέρον σε εφαρμογές όπως οι αραιές αναπαραστάσεις (sparse representations) και η συμπιεστική δειγματοληψία (compressed sensing). Όμως, ETFs δεν υπάρχουν για οποιεσδήποτε διαστάσεις, ενώ η κατασκευή τους έχει αποδειχθεί ιδιαίτερα δύσκολη. Στην παρούσα διατριβή προτείνονται δύο μέθοδοι για την κατασκευή προσεγγιστικών ETFs, Κίνητρο για τη κατασκευή των προτεινόμενων frames αποτελεί η εφαρμογή τους σε προβλήματα αραιών αναπαραστάσεων και συμπιεστικής δειγματοληψίας. Οι συγκεκριμένες εφαρμογές αφορούν σήματα που μπορούν να παρασταθούν από λίγους μη μηδενικούς συ ντελεστές, δηλαδή, αραιά ή συμπιέσιμα σήματα, και έχουν γνωρίσει ιδιαίτερη ανάπτυξη την τελευταία δεκαετία, διότι παρέχουν τη δυνατότητα συμπαγών αναπαραστάσεων, χρήσιμων για διάφορους τύπους δεδομένων. Το μαθηματικό μοντέλο που βρίσκεται στην καρδιά των συγκεκριμένων αναπαραστάσεων είναι ένα υπο-ορισμένο γραμμικό σύστημα, με πλήθος εξισώσεων μικρότερο από το πλήθος των αγνώστων, Ο υπολογισμός της αραιότερης λύσης, δηλαδή, της λύσης με το μικρότερο πλήθος μη μηδενικών συντελεστών, είναι εφικτός με τη χρήση κατάλληλων αριθμητικών μεθόδων. Οι πιο γνωστοί αλγόριθμοι είναι ο Orthogonal Matching Pursuit (OMP) και o Basis Pursuit (BP), Η αναπαράσταση ενός σήματος με λίγους μη μηδενικούς συντελεστές, συνήθως, επι τυγχάνεται με τη χρήση ενός υπερπλήρους συστήματος αναπαράστασης, που είναι γνωστό ως λεξικό (dictionary), Η αποδοτική λειτουργία των αλγορίθμων που χρησιμοποιούνται για τον υπολογισμό των μη μηδενικών συντελεστών προϋποθέτει την ικανοποίηση συγκε κριμένων συνθηκών. Μια από αυτές απαιτεί το λεξικό να έχει τη μορφή ενός incoherent UNTF, Ωστόσο, γνωστά λεξικά αυτής της μορφής δεν οδηγούν σε ικανοποιητικό επίπεδο αραιότητας. Για το λόγο αυτό πολλά λεξικά έχουν σχεδιαστεί χρησιμοποιώντας τεχνικές εκμάθησης. Συνήθως, όμως, τα λεξικά αυτού του τύπου δεν ικανοποιούν τις συνθήκες που απαιτούν οι αλγόριθμοι υπολογισμού της αραιής αναπαράστασης, Η θεωρία της συμπιεστικής δειγματοληψίας καθιστά δυνατή την ανάκτηση ενός σήματος από ένα πλήθος ελλιπών μετρήσεων, Η συμπιεστική δειγματοληψία αφορά σήματα που είναι αραιά ή συμπιέσιμα και χρησιμοποιεί έναν μηχανισμό δειγματοληψίας που υλοποιείται με τη βοήθεια κατάλληλου πίνακα, γνωστού ως πίνακα προβολών (projection matrix). Σύμφωνα με τη θεωρία, ο πίνακας αυτός πρέπει να έχει την ιδιότητα περιορισμένης ισομετρίας (re stricted isometry property-RIP). Η κατασκευή τέτοιων πινάκων είναι ιδιαίτερα δύσκολη, διότι η επαλήθευση της RIP απαιτεί συνδυαστικούς υπολογισμούς. Οι πιο γνωστοί πίνακες που ικανοποιούν τη RIP με μεγάλη πιθανότητα είναι οι τυχαίοι πίνακες Gauss και Bernoulli, Για τους πίνακες αυτούς υπάρχουν θεωρητικά αποτελέσματα που αποδεικνύουν ότι είναι εφικτή η ανάκτηση ενός σήματος μήκους Λ' με s μη μηδενικούς συντελεστές, όταν το πλήθος μετρήσεων είναι της τάξης O(s logiV). Σύμφωνα πρόσφατα αποτελέσματα, η παραπάνω συνθήκη ανάκτησης ισχύει και όταν ο πίνακας προβολών έχει τη μορφή ενός incoherent UNTF, Συνεπώς, μια νέα στρατηγική κατασκευής πινάκων προβολών περιλαμβάνει την κατασκευή πινάκων με χαμηλή αμοιβαία συνάφεια και μικρή φασματική νόρμα. Ελάχιστες τιμές τόσο για την αμοιβαία συνάφεια όσο και για τη φασματική νόρμα συναντώνται στα ETFs, Επομένως, οι προτεινόμενες μέθοδοι στοχεύουν στην κατασκευή προσεγγιστικών ETFs, Η πρώτη μέθοδος χρησιμοποιεί αποτελέσματα από τη θεωρία των frames και βασίζεται σε ιδέες που χρησιμοποιούνται στη μέθοδο των εναλλασσόμενων προβολών (alternating projections). Τα frames που παράγει έχουν τη μορφή UNTFs και εμφανίζουν μικρή αμοιβαία συνάφεια, οπότε αποτελούν incoherent UNTFs, Η δεύτερη μέθοδος βασίζεται σε πρόσφατα αποτελέσματα που αποδειχνύουν την ύπαρξη αμφιμονο σήμαντης αντιστοιχίας μεταξύ ETFs και γραφών συγκεκριμένου τύπου, Η ύπαρξη ενός ETF καθορίζεται από έναν πίνακα, γνωστό ως πίνακα signature, που έχει τη μορφή πίνακα γειτονίας γράφου και το φάσμα του αποτελείται από δύο διακριτές ιδιοτιμές. Αντιμετωπίζο ντας την κατασκευή του πίνακα signature ως ένα αντίστροφο πρόβλημα ιδιοτιμών (inverse eigenvalue problem), προτείνουμε έναν αριθμητικό αλγόριθμο που οδηγεί σε προσεγγιστική λύση, Η δεύτερη μέθοδος παράγει προσεγγιστικά ETFs, με διανύσματα που εμφανίζουν παρόμοια συσχέτιση και σχεδόν βέλτιστη φασματική νόρμα. Οι προτεινόμενες κατασκευές χρησιμοποιούνται ως πίνακες προβολών για συμπιεστική δειγματοληψία, βελτιώνοντας σημαντικά την απόδοση των σχετικών αλγορίθμων στην ανά κτηση αραιών σημάτων. Επειδή πολλά σήματα έχουν αραιές αναπαραστάσεις ως προς υπερ πλήρη λεξικά, χρησιμοποιούμε τα προτεινόμενα incoherent UNTFs για την κατασκευή βελτιστοποιημένων πινάκων προβολών σε σχέση με δεδομένο λεξικό. Ένας επιπλέον τρόπος για την αξιοποίηση των προτεινόμενων κατασκευών στην επίλυση υπο-ορισμένων γραμμικών συστημάτων είναι η τεχνική της προρρύθμισης. Εφαρμόζοντας προρρύθμιση σε αραιές αναπαραστάσεις οδηγούμαστε σε καλύτερη απόδοση των αλγορίθμων που χρησιμο ποιούνται για τον υπολογισμό των μη μηδενικών συντελεστών. Στη συμπιεστική δειγματο ληψία η προρρύθμιση βελτιώνει την ανάκτηση του σήματος, όταν χρησιμοποιούνται δυαδικοί πίνακες προβολών. Σημειώνουμε ότι οι δυαδικοί πίνακες προβολών παρουσιάζουν ευκολό τερη πρακτική υλοποίηση. Εκτός από τις αραιές αναπαραστάσεις και τη συμπιεστική δειγματοληψία, μια από τις προτεινόμενες κατασκευές είναι κατάλληλη για τη σχεδίαση σχεδόν βέλτιστων κωδικών (codes) ή ακολουθιών εξάπλωσης (spreading sequences) σε συστήματα σύγχρονου CDMA, Είναι γνωστό ότι οι βέλτιστες ακολουθίες έχουν τη μορφή equal norm tight frames και οδηγούν σε μεγιστοποίηση του ρυθμού μετάδοσης, ενώ ελαχιστοποιούν την παρεμβολή μεταξύ χρηστών. Ωστόσο, όταν το πλήθος των ενεργών χρηστών είναι μεταβαλλόμενο, τότε οι ακολουθίες είναι βέλτιστες μόνο όταν έχουν τη μορφή ETFs, Δυστυχώς, μόνο λίγες κατασκευές ETFs υπάρχουν στη βιβλιογραφία. Το σύστημα κωδικών που παρουσιάζεται εδώ έχει τη μορφή προσεγγιστικών ETFs και ελαχιστοποιεί την παρεμβολή μεταξύ χρηστών ακόμα και όταν κάποιοι χρήστες είναι ανενεργοί.
Τα frames είναι υπερπλήρη συστήματα που παράγουν έναν διανυσματικό χώρο και θεωρούνται επέκταση των ορθοκανονικών βάσεων. Στην επεξεργασία σήματος, τα frames έγιναν γνωστά χάρη στα wavelets. Άλλοι τύποι frames έχουν χρησιμοποιηθεί σε ποικίλες εφαρμογές, όπως είναι η κωδικοποίηση, η εύρωστη μετάδοση και τα συστήματα πολλαπλής προσπέλασης με διαίρεση κώδικα (Code Division Multiple Aeeess-CDMA), Η υπερπληρό- τητα θεωρείται το πιο σημαντικό χαρακτηριστικό των frames, διότι προσφέρει ευελιξία στην αναπαράσταση ενός σήματος και διευκολύνει την επεξεργασία. Ένα frame με πεπερασμένο πλήθος διανυσμάτων που παράγει τον ///-διάστατο διανυ- σματικό χώρο Η™, συνήθως, αναπαριστάται από έναν πίνακα μεγέθους m x Ν , που έχει ως στήλες τα διανύσματα του frame, δηλαδή, F = [/ ι f 2 ... / at ], m < Ν , fk Ε Η™, k = Ι,.,.,Ν. Ως πιο σημαντικές ιδιότητες ενός frame θεωρούνται η αμοιβαία συνάφεια (mutual coherence) και η φασματική νόρμα (spectral norm). Η αμοιβαία συνάφεια αποτελεί ένα μέτρο της μέγιστης συσχέτισης των διανυσμάτων του frame και εκφράζει την ομοιότητα μεταξύ των στηλών του πίνακα F. Η φασματική νόρμα αποτελεί μέτρο της μέγιστης δυνατής διαστολής ενός μοναδιαίου διανύσματος, όταν αυτό πολλαπλασιαστεί με το frame. Οι δύο ιδιότητες ορίζουν συγκεκριμένες κατηγορίες frames. Τα unit norm tight frames (UNTFs) εμφανίζουν τη μικρότερη δυνατή φασματική νόρμα. Τα συγκεκριμένα frames έχουν στήλες μοναδιαίου μέτρου και ορθογώνιες γραμμές ίσου μέτρου. Όταν ένα UNTF εμφανίζει μικρή αμοιβαία συνάφεια, τότε χαρακτηρίζεται ως incoherent UNTF. Η ελάχιστη δυνατή αμοιβαία συνάφεια συναντάται στα equiangular tight frames (ETFs). Τα διανύσματα των ETFs εμφανίζουν ταυτόσημη συσχέτιση και τα frames αυτού του τύπου θεωρούνται ως η καλύτερη προσέγγιση ορθοκανονικών βάσεων. Τα ETFs έχουν προταθεί για την επίτευξη εύρωστης μετάδοσης σε συστήματα επικοινω νίας, καθώς και για την ελαχιστοποίηση της παρεμβολής μεταξύ των χρηστών σε συστήματα πολλαπλής προσπέλασης. Χάρη στην ελάχιστη αμοιβαία συνάφεια που εμφανίζουν, παρου σιάζουν ενδιαφέρον σε εφαρμογές όπως οι αραιές αναπαραστάσεις (sparse representations) και η συμπιεστική δειγματοληψία (compressed sensing). Όμως, ETFs δεν υπάρχουν για οποιεσδήποτε διαστάσεις, ενώ η κατασκευή τους έχει αποδειχθεί ιδιαίτερα δύσκολη. Στην παρούσα διατριβή προτείνονται δύο μέθοδοι για την κατασκευή προσεγγιστικών ETFs, Κίνητρο για τη κατασκευή των προτεινόμενων frames αποτελεί η εφαρμογή τους σε προβλήματα αραιών αναπαραστάσεων και συμπιεστικής δειγματοληψίας. Οι συγκεκριμένες εφαρμογές αφορούν σήματα που μπορούν να παρασταθούν από λίγους μη μηδενικούς συ ντελεστές, δηλαδή, αραιά ή συμπιέσιμα σήματα, και έχουν γνωρίσει ιδιαίτερη ανάπτυξη την τελευταία δεκαετία, διότι παρέχουν τη δυνατότητα συμπαγών αναπαραστάσεων, χρήσιμων για διάφορους τύπους δεδομένων. Το μαθηματικό μοντέλο που βρίσκεται στην καρδιά των συγκεκριμένων αναπαραστάσεων είναι ένα υπο-ορισμένο γραμμικό σύστημα, με πλήθος εξισώσεων μικρότερο από το πλήθος των αγνώστων, Ο υπολογισμός της αραιότερης λύσης, δηλαδή, της λύσης με το μικρότερο πλήθος μη μηδενικών συντελεστών, είναι εφικτός με τη χρήση κατάλληλων αριθμητικών μεθόδων. Οι πιο γνωστοί αλγόριθμοι είναι ο Orthogonal Matching Pursuit (OMP) και o Basis Pursuit (BP), Η αναπαράσταση ενός σήματος με λίγους μη μηδενικούς συντελεστές, συνήθως, επι τυγχάνεται με τη χρήση ενός υπερπλήρους συστήματος αναπαράστασης, που είναι γνωστό ως λεξικό (dictionary), Η αποδοτική λειτουργία των αλγορίθμων που χρησιμοποιούνται για τον υπολογισμό των μη μηδενικών συντελεστών προϋποθέτει την ικανοποίηση συγκε κριμένων συνθηκών. Μια από αυτές απαιτεί το λεξικό να έχει τη μορφή ενός incoherent UNTF, Ωστόσο, γνωστά λεξικά αυτής της μορφής δεν οδηγούν σε ικανοποιητικό επίπεδο αραιότητας. Για το λόγο αυτό πολλά λεξικά έχουν σχεδιαστεί χρησιμοποιώντας τεχνικές εκμάθησης. Συνήθως, όμως, τα λεξικά αυτού του τύπου δεν ικανοποιούν τις συνθήκες που απαιτούν οι αλγόριθμοι υπολογισμού της αραιής αναπαράστασης, Η θεωρία της συμπιεστικής δειγματοληψίας καθιστά δυνατή την ανάκτηση ενός σήματος από ένα πλήθος ελλιπών μετρήσεων, Η συμπιεστική δειγματοληψία αφορά σήματα που είναι αραιά ή συμπιέσιμα και χρησιμοποιεί έναν μηχανισμό δειγματοληψίας που υλοποιείται με τη βοήθεια κατάλληλου πίνακα, γνωστού ως πίνακα προβολών (projection matrix). Σύμφωνα με τη θεωρία, ο πίνακας αυτός πρέπει να έχει την ιδιότητα περιορισμένης ισομετρίας (re stricted isometry property-RIP). Η κατασκευή τέτοιων πινάκων είναι ιδιαίτερα δύσκολη, διότι η επαλήθευση της RIP απαιτεί συνδυαστικούς υπολογισμούς. Οι πιο γνωστοί πίνακες που ικανοποιούν τη RIP με μεγάλη πιθανότητα είναι οι τυχαίοι πίνακες Gauss και Bernoulli, Για τους πίνακες αυτούς υπάρχουν θεωρητικά αποτελέσματα που αποδεικνύουν ότι είναι εφικτή η ανάκτηση ενός σήματος μήκους Λ' με s μη μηδενικούς συντελεστές, όταν το πλήθος μετρήσεων είναι της τάξης O(s logiV). Σύμφωνα πρόσφατα αποτελέσματα, η παραπάνω συνθήκη ανάκτησης ισχύει και όταν ο πίνακας προβολών έχει τη μορφή ενός incoherent UNTF, Συνεπώς, μια νέα στρατηγική κατασκευής πινάκων προβολών περιλαμβάνει την κατασκευή πινάκων με χαμηλή αμοιβαία συνάφεια και μικρή φασματική νόρμα. Ελάχιστες τιμές τόσο για την αμοιβαία συνάφεια όσο και για τη φασματική νόρμα συναντώνται στα ETFs, Επομένως, οι προτεινόμενες μέθοδοι στοχεύουν στην κατασκευή προσεγγιστικών ETFs, Η πρώτη μέθοδος χρησιμοποιεί αποτελέσματα από τη θεωρία των frames και βασίζεται σε ιδέες που χρησιμοποιούνται στη μέθοδο των εναλλασσόμενων προβολών (alternating projections). Τα frames που παράγει έχουν τη μορφή UNTFs και εμφανίζουν μικρή αμοιβαία συνάφεια, οπότε αποτελούν incoherent UNTFs, Η δεύτερη μέθοδος βασίζεται σε πρόσφατα αποτελέσματα που αποδειχνύουν την ύπαρξη αμφιμονο σήμαντης αντιστοιχίας μεταξύ ETFs και γραφών συγκεκριμένου τύπου, Η ύπαρξη ενός ETF καθορίζεται από έναν πίνακα, γνωστό ως πίνακα signature, που έχει τη μορφή πίνακα γειτονίας γράφου και το φάσμα του αποτελείται από δύο διακριτές ιδιοτιμές. Αντιμετωπίζο ντας την κατασκευή του πίνακα signature ως ένα αντίστροφο πρόβλημα ιδιοτιμών (inverse eigenvalue problem), προτείνουμε έναν αριθμητικό αλγόριθμο που οδηγεί σε προσεγγιστική λύση, Η δεύτερη μέθοδος παράγει προσεγγιστικά ETFs, με διανύσματα που εμφανίζουν παρόμοια συσχέτιση και σχεδόν βέλτιστη φασματική νόρμα. Οι προτεινόμενες κατασκευές χρησιμοποιούνται ως πίνακες προβολών για συμπιεστική δειγματοληψία, βελτιώνοντας σημαντικά την απόδοση των σχετικών αλγορίθμων στην ανά κτηση αραιών σημάτων. Επειδή πολλά σήματα έχουν αραιές αναπαραστάσεις ως προς υπερ πλήρη λεξικά, χρησιμοποιούμε τα προτεινόμενα incoherent UNTFs για την κατασκευή βελτιστοποιημένων πινάκων προβολών σε σχέση με δεδομένο λεξικό. Ένας επιπλέον τρόπος για την αξιοποίηση των προτεινόμενων κατασκευών στην επίλυση υπο-ορισμένων γραμμικών συστημάτων είναι η τεχνική της προρρύθμισης. Εφαρμόζοντας προρρύθμιση σε αραιές αναπαραστάσεις οδηγούμαστε σε καλύτερη απόδοση των αλγορίθμων που χρησιμο ποιούνται για τον υπολογισμό των μη μηδενικών συντελεστών. Στη συμπιεστική δειγματο ληψία η προρρύθμιση βελτιώνει την ανάκτηση του σήματος, όταν χρησιμοποιούνται δυαδικοί πίνακες προβολών. Σημειώνουμε ότι οι δυαδικοί πίνακες προβολών παρουσιάζουν ευκολό τερη πρακτική υλοποίηση. Εκτός από τις αραιές αναπαραστάσεις και τη συμπιεστική δειγματοληψία, μια από τις προτεινόμενες κατασκευές είναι κατάλληλη για τη σχεδίαση σχεδόν βέλτιστων κωδικών (codes) ή ακολουθιών εξάπλωσης (spreading sequences) σε συστήματα σύγχρονου CDMA, Είναι γνωστό ότι οι βέλτιστες ακολουθίες έχουν τη μορφή equal norm tight frames και οδηγούν σε μεγιστοποίηση του ρυθμού μετάδοσης, ενώ ελαχιστοποιούν την παρεμβολή μεταξύ χρηστών. Ωστόσο, όταν το πλήθος των ενεργών χρηστών είναι μεταβαλλόμενο, τότε οι ακολουθίες είναι βέλτιστες μόνο όταν έχουν τη μορφή ETFs, Δυστυχώς, μόνο λίγες κατασκευές ETFs υπάρχουν στη βιβλιογραφία. Το σύστημα κωδικών που παρουσιάζεται εδώ έχει τη μορφή προσεγγιστικών ETFs και ελαχιστοποιεί την παρεμβολή μεταξύ χρηστών ακόμα και όταν κάποιοι χρήστες είναι ανενεργοί.
Περιγραφή
Λέξεις-κλειδιά
Frames, Equiangular tight frames
Θεματική κατηγορία
Frames (Information theory)
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Όνομα επιβλέποντος
Κόντης, Λυσίμαχος-Παύλος
Εξεταστική επιτροπή
Κόντης, Λυσίμαχος-Παύλος
Νίκου, Χριστόφορος
Κατσάγγελος, Άγγελος
Λύκας, Αριστείδης
Μπλέκας, Κωνσταντίνος
Παρσόπουλος, Κωνσταντίνος
Τσακαλίδης, Παναγιώτης
Νίκου, Χριστόφορος
Κατσάγγελος, Άγγελος
Λύκας, Αριστείδης
Μπλέκας, Κωνσταντίνος
Παρσόπουλος, Κωνσταντίνος
Τσακαλίδης, Παναγιώτης
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογράφία : σ. 103-113
Ονόματα συντελεστών
Αριθμός σελίδων
118 σ.