1,721,092 research outputs found
On nondecreasing sequences of regularization parameters for nonstationary iterated Tikhonov
No full textNonstationary iterated Tikhonov is an iterative regularization
method that requires a strategy for defining the Tikhonov regularization
parameter at each iteration and an early termination of the iterative process.
A classical choice for the regularization parameters is a decreasing geometric
sequence which leads to a linear convergence rate. The early iterations
compute quickly a good approximation of the true solution, but the main
drawback of this choice is a rapid growth of the error for later iterations.
This implies that a stopping criteria, e.g. the discrepancy principle, could
fail in computing a good approximation. In this paper we show by a filter
factor analysis that a nondecreasing sequence of regularization parameters can
provide a rapid and stable convergence. Hence, a reliable stopping criteria is
no longer necessary. A geometric nondecreasing sequence of the Tikhonov
regularization parameters into a fixed interval is proposed and numerically
validated for deblurring problems
PRIN2012: Matrici Strutturate nella Ricostruzione di Segnali e Immagini
No full textl progetto si pone alla frontiera tra la ricerca di base nel campo dell'algebra lineare numerica strutturata e le applicazioni legate alla ricostruzione di immagini, con particolare attenzione al caso di immagini sfocate o derivanti dall'emissione di raggi X. Infatti, molteplici strumenti algebrici strutturati sviluppati in passato possono essere utilizzati in problemi concreti con la prospettiva di miglioramenti sostanziali, sia nell'efficienza degli algoritmi (costo computazionale, occupazione di memoria, ecc.) sia nell'accuratezza dei modelli, e quindi nella qualità della soluzione calcolata. D'altra parte nuovi esempi applicativi in ambito biomedico, astronomico, civile, ecc., pongono nuove questioni teoriche e computazionali in algebra lineare strutturata che meritano particolare attenzione. Proprio in tale contesto si vuole coniugare l'esperienza che alcuni componenti del progetto hanno maturato nell'ambito dell'algebra lineare numerica, con le applicazioni concrete su cui altri componenti già lavorano da anni grazie a collaborazioni in essere con centri di ricerca biomedica e astrofisica.
Le applicazioni di cui ci occuperemo in questo progetto saranno principalmente: A.1) Ricostruzione d'immagini sfocate e affette da rumore.
A.2) Ricostruzione di oggetti mediante raggi X o dispersione da micro-onde. A.3) Classificazione e analisi di dati biomedici.
In molte delle applicazioni citate la presenza del rumore riveste un ruolo non trascurabile e spesso si tratta di problemi malposti discreti (in quanto i dati a disposizione sono forniti in forma di matrici o tensori e tali problemi discreti possono essere considerati come una discretizzazione di problemi malposti) che necessitano quindi di regolarizzazione. In alcuni casi è inoltre utile combinare strumenti di algebra lineare strutturata con tecniche di ottimizzazione o di approssimazione.
Le tecniche numeriche che ci proponiamo di studiare sono essenzialmente di tre tipi: B.1) Metodi iterativi regolarizzanti e tecniche di accelerazione.
B.2) Metodi numerici per modelli di regolarizzazione non lineari.
B.3) Fattorizzazioni non negative e schemi di suddivisione.
Per concludere, si osserva che il calcolo di soluzioni accurate per le applicazioni di cui ai punti A.1-A.3 richiede solitamente di imporre vincoli non lineari per preservare la non negatività e/o la sparsità della soluzione. I metodi numerici che ne derivano possono quindi essere computazionalmente costosi e trarre notevole beneficio dall'utilizzo di strumenti di algebra lineare numerica in grado di sfruttare efficacemente la struttura e le proprietà del problema in oggetto. A titolo di esempio, tecniche di precondizionamento (eventualmente multilivello) regolarizzante sviluppate al punto B.1 potrebbero essere combinate con vincoli di sparsità e/o non negatività ottenendo nuovi metodi numerici per il punto B.2, applicabili con successo sia ai problemi del punto A.1 che ad alcune applicazioni in A.2 e in A.3
Analisi di strutture nella ricostruzione di immagini e monumenti
No full text1. Definizione ed analisi teorica di nuovi operatori di proiezione per metodi multigrid basati solo sulle informazioni algebriche del problema, applicabili sia a discretizzazioni
agli elementi finiti, sia a problemi di ricostruzione di immagini ed a matrici di grafo.
2. Definizione e studio di metodi multilivello regolarizzanti per la ricostruzione di immagini sfocate ed affette da rumore, combinando tecniche nonlineari di edge-preserving
con operatori di trasferimento di griglia regolarizzanti che preservano la struttura.
3. Applicazione di condizioni al contorno in grado di preservare segnali smooth a tecniche di regolarizzazione accurate e solitamente computazionalmente costose, (e.g., Total Variation (TV), Regularized Total Least Square (RTLS), preconditioned GMRES, etc.), ricorrendo a trasformate discrete veloci di recente sviluppo (generalizzazione di FFT).
4. Studio di metodi impliciti per EDP paraboliche degeneri con applicazioni sia ai modelli di degrado monumentale sia a problemi di ricostruzione di immagini sfocate con termine regolarizzante non lineare.
5. Analisi spettrale di matrici, con struttura nascosta, non Hermitiane associate a simboli a blocchi con applicazioni al precondizionamento di EDP, alla regolarizzazione non lineare, ed a problemi di ricostruzione di segnali o immagini in cui alcuni campionamenti non sono disponibili o in cui le dimensioni del dominio introducono evidenti distorsioni
di tipo prospettico
Precondizionamento e metodi Multigrid per il calcolo veloce di soluzioni accurate
No full textLa struttura e gli obiettivi del progetto possono essere sintetizzati come segue.
1. Precondizionamento per alcune EDP ellittiche/paraboliche, anche degeneri.
2. Analisi di convergenza di metodi multigrid con particolare attenzioni agli operatori di proiezione basati su smoothed aggregation.
3. Precondizionamento regolarizzante per problemi malposti sia lineari sia nonlineari.
4. Metodi multigrid regolarizzanti per la ricostruzione di immagini sfocate
Programma Giovani Ricercatori - GNCS
No full textIl presente progetto di ricerca si articola nei seguenti argomenti
principali:
1) Metodi multilivello per la ricostruzione di immagini.
Si vorrebbe investigare le possibili relazioni
tra tali tecniche multilivello e le wavelets al fine di
definire strategie di proiezione efficaci e computazionalmente
vantaggiose.
2) Ricostruzione di immagini sfuocate.
Ci si propone di investigare la combinazione di modelli basati
sull'imposizione di opportune condizioni al contorno con
tecniche di regolarizzazione basate su Total Variation o PDE,
eventualmente sfruttando anche strategie multilivello di cui al punto precedente.
Questo permetterebbe di ottenere ricostruzioni
accurate con un costo computazionale contenuto.
3) Analisi di convergenza di metodi multigrid per matrici associate ad un simbolo. Si e' interessati ad un'estensione della classica teoria di congervenza
di metodi multigrid per PDE sviluppata utilizzando come strumento
principale la ``local Fourier analysis''.
4) Risoluzione di sistemi lineari con strutture localmente Toeplitz.
L'analisi spettrale e la definizione di strategie di
precondizionamento per matrici di Toeplitz o localmente
Toeplitz sono state ampliamente investigate in letteratura.
Recentemente mi sono interessato dell'applicazione di tali
tecniche a problemi specifici come PDE paraboliche o PDE
discretizzate mediante tecniche di collocazione con
basi radiali
An Iterative Multigrid Regularization Method for Toeplitz Discrete Ill-Posed Problems
No full textIterative regularization multigrid methods have been successful applied to signal/image deblurring problems. When zero-Dirichlet boundary conditions are imposed the deblurring matrix has a Toeplitz structure and it is potentially full. A crucial task of a multilevel strategy is to preserve the Toeplitz structure at the coarse levels which can be exploited to obtain fast computations. The smoother has to be an iterative regularization method. The grid transfer operator should preserve the regularization property of the smoother. This paper improves the iterative multigrid method proposed in [11] introducing a wavelet soft-thresholding denoising post-smoother. Such postsmoother avoids the noise amplification that is the cause of the semi-convergence of iterative regularization methods and reduces ringing effects. The resulting iterative multigrid regularization method stabilizes the iterations so that and imprecise (over) estimate of the stopping iteration does not have a deleterious effect on the computed solution. Numerical examples of signal and image deblurring problems confirm the effectiveness of the proposed method
A Multigrid method for restoration and regularization of images with Dirichlet boundary conditions
No full textIn many 2D image restoration problems, such as image deblurring with Dirichlet boundary conditions, we deal with two-level linear systems whose coefficient matrix is a banded block Toeplitz matrix with banded Toeplitz blocks (BTTB). Usually, these matrices are ill-conditioned since they are associated to generating functions which vanish at (π, π) or in neighborhood of it. In this work, we solve such BTTB systems by applying an Algebraic Multi-Grid method (AMG). The technique we propose has an optimality property, i.e., its cost is of O(n1 " n2) arithmetic operations, where n1 x n2 is the size of the images. Unfortunately, in the case of images affected by noise, our AMG method does not provide satisfactory regularization effects. Therefore, we propose two Tikhonov-like techniques, based on a regularization parameter, which can be applied to AMG method in order to reduce the noise effects
An algebraic generalization of local Fourier analysis for grid transfer operators in multigrid based on Toeplitz matrices
No full textLocal Fourier analysis (LFA) is a classical tool for proving convergence theorems for multigrid methods (MGMs). In particular, we are interested in optimal convergence, i.e. convergence rates that are independent of the problem size. For elliptic partial differential equations (PDEs), a well-known optimality result requires that the sum of the orders of the grid transfer operators is not lower than the order of the PDE approximated. Analogously, when dealing with MGMs for Toeplitz matrices, a well-known optimality condition concerns the position and the order of the zeros of the symbols of the grid transfer operators. In this work we show that in the case of elliptic PDEs with constant coefficients, the two different approaches lead to an equivalent condition. We argue that the analysis for Toeplitz matrices is an algebraic generalization of the LFA, which allows to deal not only with differential problems but also for instance with integral problems. The equivalence of the two approaches gives the possibility of using grid transfer operators with different orders also for MGMs for Toeplitz matrices. We give also a class of grid transfer operators related to the B-spline's refinement equation and study their geometric properties. Numerical experiments confirm the correctness of the proposed analysis
A multigrid for image deblurring with Tikhonov regularization
No full textIn the resolution of certain image deblurring problems with given boundary conditions we obtain two-level structured linear systems. In the case of shift-invariant point spread function with Dirichlet (zero) boundary conditions, the blurring matrices are block Toeplitz matrices with Toeplitz blocks. If the periodic boundary conditions are used, then the involved structures become block circulant with circulant blocks. Furthermore, Gaussian-like point spread functions usually lead to numerically banded matrices which are ill-conditioned since they are associated to generating functions that vanish in a neighbourhood of (π,π). We solve such systems by applying a multigrid method. The proposed technique shows an optimality property, i.e. its cost is of O(N) arithmetic operations (like matrix–vector product), where N is the size of the linear system. In the case of images affected by noise we use two Tikhonov regularization techniques to reduce the noise effects
A V-cycle Multigrid for multilevel matrix algebras: proof of optimality
No full textWe analyze the convergence rate of a multigrid method for multilevel
linear systems whose coefficient matrices are generated by a real
and nonnegative multivariate polynomial and belong to multilevel
matrix algebras like circulant, tau, Hartley, or are of Toeplitz type.
In the case of matrix algebra linear systems, we prove that the
convergence rate is independent of the system dimension even in
presence of asymptotical ill-conditioning (this happens iff
takes the zero value). More precisely, if the -level coefficient
matrix has partial dimension at level , with ,
then the size of the system is N(\mi{n})=\prod_{r=1}^d n_r,
\mi{n}=(n_1, \dots, n_d), and O(N(\mi{n})) operations are
required by the considered -cycle Multigrid in order to compute the solution
within a fixed accuracy. Since the total arithmetic cost is
asymptotically equivalent to the one of a matrix-vector product, the
proposed method is optimal. Some numerical experiments concerning
linear systems arising in 2D and 3D applications are considered
and discussed
- …
