Muchos métodos modernos estadísticamente eficientes vienen con enormes desafíos computacionales, lo que a menudo conduce a problemas de optimización a gran escala. En este trabajo, examinamos tales problemas computacionales para los métodos de estimación recientemente desarrollados en regresión no paramétrica con un enfoque específico en la reducción de ruido de imágenes. Consideramos en particular ciertos estimadores multiescala variacionales que son óptimos estadísticamente en un sentido minimax, pero intensivos computacionalmente. Dicho estimador se calcula como el minimizador de una funcionalidad de suavidad (por ejemplo, la norma TV) sobre la clase de todos los estimadores de manera que ninguno de sus coeficientes con respecto a un diccionario multiescala dado sea estadísticamente significativo. El estimador multiescala Nemirowski-Dantzig (MIND) obtenido de esta manera puede incorporar cualquier funcionalidad de suavidad convexa y combinarla con un diccionario adecuado que incluya wavelets, curvelets y shearlets. El cálculo de MIND en general requiere resolver un problema de optimización convexa restringida de alta dimensionalidad con una estructura específica de las restricciones inducida por el criterio estadístico de prueba multiescala. Para resolver esto explícitamente, discutimos tres enfoques algorítmicos diferentes: los algoritmos de Chambolle-Pock, ADMM y Newton semisuave. Se presentan detalles algorítmicos y una implementación explícita y luego se comparan las soluciones numéricamente en un estudio de simulación y en varias imágenes de prueba. Recomendamos el algoritmo de Chambolle-Pock en la mayoría de los casos por su rápida convergencia. Destacamos que nuestro análisis también puede ser transferido a la recuperación de señales y otros problemas de reducción de ruido para recuperar objetos más generales siempre que sea posible aprovechar la fuerza estadística de los parches de datos de estructura de objeto similar.